Problem description:

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 1:

1
2
3
Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

1
2
Input: s = "abbababa", k = 1
Output: true

Constraints:

  • 1 <= s.length <= 1000
  • s consists of only lowercase English letters.
  • 1 <= k <= s.length

Solution:

bottom-up

Start from end of string

7D413DA6-DF1E-45A3-8D56-77BF0C26E807.jpeg

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        memo = defaultdict(int)
        for i in range(len(s)-2, -1, -1):
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    memo[(i,j)] = memo[(i+1, j-1)]
                else:
                    memo[(i,j)] = 1+ min(memo[(i+1, j)], memo[(i, j-1)])
        return memo[(0, len(s)-1)] <= k

We actually only need i+1th row and j-1th column

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        memo = defaultdict(int)
        tmp, prev = 0, 0
        for i in range(len(s)-2, -1, -1):
            prev = 0 # // 'prev' stores the value at memo[i+1][j-1];
            for j in range(i+1, len(s)):
                tmp = memo[j] # // Store the value of memo[i+1][j] temporarily.
                if s[i] == s[j]:
                    memo[j] = prev
                else:
                    # memo[(i,j)] = 1 + min(memo[(i+1,j)], memo[(i, j-1)])
                    # memo[j] will contain the value for memo[i+1][j]
                    # memo[j-1] will contain the value for memo[i][j-1]
                    memo[j] = 1+ min(memo[j], memo[j-1])
                # Copy the value of memo[i+1][j] to `prev`
                # For the next iteration when j=j+1
                # `prev` will hold the value memo[i+1][j-1];
                prev = tmp
        return memo[len(s)-1] <= k

time complexity: $O()$
space complexity: $O()$
reference:
related problem: