Valid Palindrome III - Practice Coding Problems

Valid Palindrome III - Problem

Given a string s and an integer k, return true if s is a k-palindrome.

A string is k-palindrome if it can be transformed into a palindrome by removing at most k characters from it.

Example:

For string "abcdeca" and k = 2, we can remove characters at positions 1 and 4 ('b' and 'e') to get "acdca", which can be rearranged to form palindrome "aceca". However, this problem asks if we can form a palindrome by removing characters while maintaining their relative order.

Input & Output

Example 1 — Basic k-palindrome

$ Input: s = "abcdeca", k = 2

› Output: true

💡 Note: We can remove 'b' and 'e' to get "acdca", then rearrange to "aceca" (palindrome). Actually, by just removing 'b' and 'e' while keeping order, we get "acdca" which needs 2 more deletions to become "aca" (palindrome). Total = 2 ≤ k.

Example 2 — Already palindrome

$ Input: s = "abcba", k = 1

› Output: true

💡 Note: String is already a palindrome, needs 0 deletions which is ≤ k=1.

Example 3 — Not enough deletions

$ Input: s = "abc", k = 1

› Output: false

💡 Note: To make "abc" a palindrome, we need to delete at least 2 characters (e.g., delete 'b' and 'c' to get "a"). Since 2 > k=1, return false.

Constraints

1 ≤ s.length ≤ 1000
0 ≤ k ≤ s.length
s consists only of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given string "abcdeca" and k=2 deletions allowed

Find Min Deletions

Calculate minimum deletions needed using DP

Compare with k

Check if min deletions ≤ k

Key Takeaway

🎯 Key Insight: Use DP to find minimum deletions needed, compare with k limit

Asked in

G Google 35 a Amazon 28 M Microsoft 22

The key insight is to find the minimum number of character deletions needed to make the string a palindrome, then check if it's ≤ k. Best approach uses 2D Dynamic Programming with bottom-up table building. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization - Top-Down DP	O(n²)	O(n²)	Use recursive approach with memoization to find minimum deletions needed
2D Dynamic Programming	O(n²)	O(n²)	Build bottom-up DP table to find minimum deletions efficiently
Brute Force - Try All Combinations	O(2^n × n)	O(n)	Generate all possible subsequences and check if any palindrome exists with ≤ k deletions

Memoization - Top-Down DP — Algorithm Steps

Step 1: Define recursive function to find min deletions from left to right pointers
Step 2: If characters match, move both pointers inward
Step 3: If characters don't match, try deleting from left or right, take minimum
Step 4: Use memoization to cache subproblem results

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Characters

If s[left] == s[right], recurse inward

Try Both Deletions

If different, try deleting left or right character

Cache Result

Store minimum deletions for this subproblem

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

int memo[1000][1000];
char s[1001];
int sLen;

int minDeletions(int left, int right) {
    if (left >= right) {
        return 0;
    }
    
    if (memo[left][right] != -1) {
        return memo[left][right];
    }
    
    int result;
    if (s[left] == s[right]) {
        result = minDeletions(left + 1, right - 1);
    } else {
        // Try deleting from left or right, take minimum
        int deleteLeft = 1 + minDeletions(left + 1, right);
        int deleteRight = 1 + minDeletions(left, right - 1);
        result = deleteLeft < deleteRight ? deleteLeft : deleteRight;
    }
    
    memo[left][right] = result;
    return result;
}

bool solution(char* str, int k) {
    strcpy(s, str);
    sLen = strlen(s);
    
    // Initialize memo array
    for (int i = 0; i < sLen; i++) {
        for (int j = 0; j < sLen; j++) {
            memo[i][j] = -1;
        }
    }
    
    int minDels = minDeletions(0, sLen - 1);
    return minDels <= k;
}

int main() {
    char str[1001];
    int k;
    
    fgets(str, sizeof(str), stdin);
    str[strcspn(str, "\n")] = 0;
    scanf("%d", &k);
    
    bool result = solution(str, k);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of the n² subproblems computed once due to memoization

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores results for all (i,j) pairs plus recursion stack

⚠ Quadratic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization - Top-Down DP — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler