Longest Palindromic Subsequence After at Most K Operations
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'. - Replacing
'a'with the previous letter results in'z'. - Replacing
'z'with the next letter results in'a'. - Replacing
'z'with the previous letter results in'y'.
Return the length of the longest palindromic subsequence of s that can be obtained after performing at most k operations.
Example 1
Input
s = "abced", k = 2Output
3After changing
s to "accec", the subsequence "ccc" forms a palindrome of length 3, which is the maximum.Example 2
Input
s = "aaazzz", k = 4Output
6After the operations, the entire string can form a palindrome of length 6.
Constraints
- 1 <= s.length <= 200
- 1 <= k <= 200
- s consists of only lowercase English letters.