Valid Palindrome III

Hard

Amazon

1 view

Topics:

StringsDynamic Programming

You are given a string s and an integer k. You are allowed to remove at most k characters from the string s. The goal is to determine if the resulting string can be a palindrome. A palindrome is a string that reads the same forwards and backward.

For example:

If s = "abcdeca" and k = 2, the output should be true. We can remove 'b' and 'e' to get "acdea", and then remove 'd' to get 'aca', which is a palindrome, meaning a total of 3 chars were removed.
If s = "abccba" and k = 0, the output should be true because the string is already a palindrome.
If s = "abbababa" and k = 1, the output should be true. The string s is already a palidrome.
If s = "abc" and k = 0, the output should be false because the string is not a palindrome, and we are not allowed to remove any characters.

Write a function that takes the string s and the integer k as input and returns true if the string can be a palindrome after removing at most k characters, and false otherwise.

Valid Palindrome III

Hard

Amazon

1 view

Topics:

StringsDynamic Programming

For example:

If s = "abcdeca" and k = 2, the output should be true. We can remove 'b' and 'e' to get "acdea", and then remove 'd' to get 'aca', which is a palindrome, meaning a total of 3 chars were removed.
If s = "abccba" and k = 0, the output should be true because the string is already a palindrome.
If s = "abbababa" and k = 1, the output should be true. The string s is already a palidrome.
If s = "abc" and k = 0, the output should be false because the string is not a palindrome, and we are not allowed to remove any characters.

Write a function that takes the string s and the integer k as input and returns true if the string can be a palindrome after removing at most k characters, and false otherwise.

Solution

Valid Palindrome III

Problem

Given a string s and an integer k, return true if s can be a palindrome after removing at most k characters from it.

Naive Solution

A brute-force approach would be to try all possible subsequences of s by removing at most k characters and check if any of the resulting subsequences are palindromes. However, this approach has exponential time complexity and is not efficient.

Optimal Solution

A better approach is to use dynamic programming. We can create a 2D table dp where dp[i][j] represents the minimum number of characters that need to be removed from the substring s[i...j] to make it a palindrome.

The base cases are:

dp[i][i] = 0 for all i (a single character is already a palindrome).
dp[i][i+1] = 0 if s[i] == s[i+1] else 1.

For the general case, we have two possibilities:

If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] (no additional characters need to be removed).
If s[i] != s[j], then dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 (remove either s[i] or s[j] and take the minimum removals).

Finally, the result is true if dp[0][n-1] <= k, where n is the length of the string s.

Edge Cases

Empty String: If the input string s is empty, it is considered a palindrome, so we return true.
k >= string length: If k is greater than or equal to the string's length, the entire string can be removed, and an empty string (which is a palindrome) can be formed. Thus, return true.

Code

def isValidPalindrome(s: str, k: int) -> bool:
    n = len(s)
    if not s:
        return True
    if k >= n:
        return True

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

    return dp[0][n-1] <= k

Time and Space Complexity

Time Complexity: O(n^2), where n is the length of the string s. We iterate through all possible substrings to fill the dp table.
Space Complexity: O(n^2) to store the dp table.

Solution

Valid Palindrome III

Problem

Given a string s and an integer k, return true if s can be a palindrome after removing at most k characters from it.

Naive Solution

Optimal Solution

The base cases are:

dp[i][i] = 0 for all i (a single character is already a palindrome).
dp[i][i+1] = 0 if s[i] == s[i+1] else 1.

For the general case, we have two possibilities:

If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] (no additional characters need to be removed).
If s[i] != s[j], then dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1 (remove either s[i] or s[j] and take the minimum removals).

Finally, the result is true if dp[0][n-1] <= k, where n is the length of the string s.

Edge Cases

Empty String: If the input string s is empty, it is considered a palindrome, so we return true.
k >= string length: If k is greater than or equal to the string's length, the entire string can be removed, and an empty string (which is a palindrome) can be formed. Thus, return true.

Code

def isValidPalindrome(s: str, k: int) -> bool:
    n = len(s)
    if not s:
        return True
    if k >= n:
        return True

    dp = [[0] * n for _ in range(n)]

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    dp[i][j] = 0
                else:
                    dp[i][j] = dp[i+1][j-1]
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1

    return dp[0][n-1] <= k

Time and Space Complexity

Time Complexity: O(n^2), where n is the length of the string s. We iterate through all possible substrings to fill the dp table.
Space Complexity: O(n^2) to store the dp table.