Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1216.html

1216. Valid Palindrome III

Level

Hard

Description

Given a string s and an integer k, find out if the given string is a K-Palindrome or not.

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

Example 1:

Input: s = “abcdeca”, k = 2

Output: true

Explanation: Remove ‘b’ and ‘e’ characters.

Constraints:

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

Solution

This problem can be solved by first obtaining the length of the longest palindromic subsequence, and check whether the difference between the string’s length and the length of the longest palindromic subsequence is less than or equal to k.

To obtain the length of the longest palindromic subsequence, use the solution to problem 516.

• Java
• C++
• Python
• Go

• class Solution {
      public boolean isValidPalindrome(String s, int k) {
          int length = s.length();
          int[][] dp = new int[length][length];
          for (int i = length - 1; i >= 0; i--) {
              dp[i][i] = 1;
              for (int j = i + 1; j < length; j++) {
                  if (s.charAt(i) == s.charAt(j))
                      dp[i][j] = dp[i + 1][j - 1] + 2;
                  else
                      dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
              }
          }
          int maxLength = dp[0][length - 1];
          return length - maxLength <= k;
      }
  }
  

• // OJ: https://leetcode.com/problems/valid-palindrome-iii/
  // Time: O(N^2)
  // Space: O(N)
  class Solution {
  public:
      bool isValidPalindrome(string s, int k) {
          string t(s.rbegin(), s.rend());
          int N = s.size();
          vector<int> dp(N + 1);
          for (int i = 0; i < N; ++i) {
              int prev = 0;
              for (int j = 0; j < N; ++j) {
                  int cur = dp[j + 1];
                  if (s[i] == t[j]) dp[j + 1] = 1 + prev;
                  else dp[j + 1] = max(dp[j + 1], dp[j]);
                  prev = cur;
              }
          }
          return dp[N] + k >= s.size();
      }
  };
  

• class Solution:
      def isValidPalindrome(self, s: str, k: int) -> bool:
          n = len(s)
          f = [[0] * n for _ in range(n)]
          for i in range(n):
              f[i][i] = 1
          for i in range(n - 2, -1, -1):
              for j in range(i + 1, n):
                  if s[i] == s[j]:
                      f[i][j] = f[i + 1][j - 1] + 2
                  else:
                      f[i][j] = max(f[i + 1][j], f[i][j - 1])
                  if f[i][j] + k >= n:
                      return True
          return False
  
  
  

• func isValidPalindrome(s string, k int) bool {
  	n := len(s)
  	f := make([][]int, n)
  	for i := range f {
  		f[i] = make([]int, n)
  		f[i][i] = 1
  	}
  	for i := n - 2; i >= 0; i-- {
  		for j := i + 1; j < n; j++ {
  			if s[i] == s[j] {
  				f[i][j] = f[i+1][j-1] + 2
  			} else {
  				f[i][j] = max(f[i+1][j], f[i][j-1])
  			}
  			if f[i][j]+k >= n {
  				return true
  			}
  		}
  	}
  	return false
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

All Problems

All Solutions