We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Palindrome III

Number: 1178

Difficulty: Hard

Paid? Yes

Companies: Meta, TikTok, Amazon

Problem Description

Given a string s and an integer k, determine 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.

Key Insights

  • The problem can be reframed as determining the minimum number of deletions needed to convert the string into a palindrome.
  • This minimum deletion count equals (length of s - length of the longest palindromic subsequence (LPS)).
  • If (s.length - LPS) is less than or equal to k, the string is k-palindrome.
  • Dynamic Programming is used to calculate the LPS in O(n^2) time.

Space and Time Complexity

Time Complexity: O(n^2) where n is the length of the string s. Space Complexity: O(n^2) for the DP table used to compute the longest palindromic subsequence.

Solution

We solve the problem by computing the length of the longest palindromic subsequence (LPS) using dynamic programming. The LPS problem involves finding the longest subsequence that is a palindrome. We set up a 2D DP table dp where dp[i][j] represents the length of the LPS within the substring s[i...j]. If s[i] equals s[j], then these two characters can contribute to the LPS; otherwise, we take the maximum of the two possible substrings (excluding either s[i] or s[j]). After computing dp[0][n-1] (which contains the LPS for the whole string), we check if the difference (s.length - LPS) is within k removals.

Code Solutions

# Function to check if the string is a k-palindrome
def isValidPalindrome(s: str, k: int) -> bool:
    n = len(s)
    # Create a 2D DP array with dimensions n x n initialized to 0
    dp = [[0] * n for _ in range(n)]
    
    # Every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1
    
    # Build the dp table in bottom-up manner
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = 2 + (dp[i + 1][j - 1] if i + 1 <= j - 1 else 0)
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    # The length of the longest palindromic subsequence
    lps = dp[0][n - 1]
    # Check if the minimum deletions needed is <= k
    return (n - lps) <= k

# Example usage
print(isValidPalindrome("abcdeca", 2))  # Expected output: True
print(isValidPalindrome("abbababa", 1)) # Expected output: True
← Back to All Questions