You are given a string s and an integer k.
In one operation, you can replace the character at any position with the next or previous letter in the alphabet (wrapping around so that 'a' is after 'z'). For example, replacing 'a' with the next letter results in 'b', and replacing 'a' with the previous letter results in 'z'. Similarly, replacing 'z' with the next letter results in 'a', and replacing 'z' with the previous letter results in 'y'.
Return the length of the longest of s that can be obtained after performing at most k operations.
Example 1:
Input: s = “abced”, k = 2
Output: 3
Explanation:
- Replace
s[1]with the next letter, andsbecomes"acced". - Replace
s[4]with the previous letter, andsbecomes"accec".
The subsequence "ccc" forms a palindrome of length 3, which is the maximum.
Example 2:
Input: s = “aaazzz“, k = 4
Output: 6
Explanation:
- Replace
s[0]with the previous letter, andsbecomes"zaazzz". - Replace
s[4]with the next letter, andsbecomes"zaazaz". - Replace
s[3]with the next letter, andsbecomes"zaaaaz".
The entire string forms a palindrome of length 6.
Constraints:
1 <= s.length <= 2001 <= k <= 200sconsists of only lowercase English letters.
from functools import lru_cache
class Solution:
def longestPalindromeSubseqAfterOperations(self, s: str, k: int) -> int:
n = len(s)
# cost(a, b) returns the minimum operations needed to change letter a to letter b
def cost(a: str, b: str) -> int:
diff = abs(ord(a) - ord(b))
return min(diff, 26 - diff)
@lru_cache(maxsize=None)
def dp(i: int, j: int, rem: int) -> int:
# Base cases:
if i > j:
return 0
if i == j:
return 1 # A single letter is a palindrome
# Option 1: Skip the left character.
res = dp(i+1, j, rem)
# Option 2: Skip the right character.
res = max(res, dp(i, j-1, rem))
# Option 3: Try to match s[i] and s[j] by spending operations if needed.
c = cost(s[i], s[j])
if c <= rem:
res = max(res, 2 + dp(i+1, j-1, rem - c))
return res
return dp(0, n-1, k)