Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1216 with 24 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1216 # by problem number
lcpy gen -s valid_palindrome_iii # by problem name
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.
Input: s = "abcdeca", k = 2
Output: true
Input: s = "abbababa", k = 1
Output: true
1 <= s.length <= 1000s consists of only lowercase English letters.1 <= k <= s.lengthclass Solution:
# Time: O(n^2)
# Space: O(n)
def is_valid_palindrome(self, s: str, k: int) -> bool:
n = len(s)
dp = [0] * n
for i in range(n - 1, -1, -1):
prev = 0
dp[i] = 1
for j in range(i + 1, n):
temp = dp[j]
if s[i] == s[j]:
dp[j] = prev + 2
else:
dp[j] = max(dp[j], dp[j - 1])
prev = temp
return n - dp[n - 1] <= k
| Time | Space |
|---|---|
| O(n^2) | O(n) |