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 palindromic subsequence of s that can be obtained after performing at mostk operations.
Input: s ="abced", k =2Output: 3Explanation:
* Replace `s[1]`with the next letter, and `s` becomes `"acced"`.* Replace `s[4]`with the previous letter, and `s` becomes `"accec"`.The subsequence `"ccc"` forms a palindrome of length 3, which is the maximum.
Input: s ="aaazzz", k =4Output: 6Explanation:
* Replace `s[0]`with the previous letter, and `s` becomes `"zaazzz"`.* Replace `s[4]`with the next letter, and `s` becomes `"zaazaz"`.* Replace `s[3]`with the next letter, and `s` becomes `"zaaaaz"`.The entire string forms a palindrome of length 6.
The goal is to find the longest palindromic subsequence from the given string using at most k operations. Each operation allows changing a character to its next or previous letter in the alphabet (with circular wrapping).
The key insight is to compute the minimum cost to make two characters match using circular distance in the alphabet. For any two characters, we can calculate the cost as the minimum of going forward or backward in the circular alphabet. Then we can decide whether to change a pair of characters (if the cost is affordable) or skip one of them to find better matching opportunities later.
Recursive DP Definition: Define solve(i, j, k) that returns the length of the longest palindromic subsequence from substring s[i...j] with at most k operations available.
Base Cases:
If i > j: No characters remain, return 0
If i == j: Single character is always a palindrome, return 1
Recursive Choices:
Skip a character: Either skip character at index i or j and recurse
Match a pair: Calculate the circular distance cost between s[i] and s[j]:
classSolution {
private:int solve(int i, int j, int k, const string& s, vector<vector<vector<int>>>& dp) {
if (i > j) return0;
if (i == j) return1;
if (dp[i][j][k] !=-1) return dp[i][j][k];
// Skip either left or right character
int ans = max(solve(i +1, j, k, s, dp), solve(i, j -1, k, s, dp));
// Calculate cost to match characters at positions i and j
int cost = min(abs(s[i] - s[j]), 26- abs(s[i] - s[j]));
// If we can afford the cost, try matching the pair
if (k >= cost) {
ans = max(ans, 2+ solve(i +1, j -1, k - cost, s, dp));
}
return dp[i][j][k] = ans;
}
public:int longestPalindromicSubsequence(string s, int k) {
int n = s.size();
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k +1, -1)));
returnsolve(0, n -1, k, s, dp);
}
};
classSolution {
privateint[][][] dp;
privateintsolve(int i, int j, int k, String s) {
if (i > j) return 0;
if (i == j) return 1;
if (dp[i][j][k]!=-1) return dp[i][j][k];
// Skip either left or right characterint ans = Math.max(solve(i + 1, j, k, s), solve(i, j - 1, k, s));
// Calculate cost to match characters at positions i and jint cost = Math.min(Math.abs(s.charAt(i) - s.charAt(j)),
26 - Math.abs(s.charAt(i) - s.charAt(j)));
// If we can afford the cost, try matching the pairif (k >= cost) {
ans = Math.max(ans, 2 + solve(i + 1, j - 1, k - cost, s));
}
return dp[i][j][k]= ans;
}
publicintlongestPalindromicSubsequence(String s, int k) {
int n = s.length();
dp =newint[n][n][k + 1];
// Initialize dp array with -1for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(dp[i][j], -1);
}
}
return solve(0, n - 1, k, s);
}
}
classSolution {
privatelateinitvar dp: Array<Array<Array<Int>>>
privatefunsolve(i: Int, j: Int, k: Int, s: String): Int {
if (i > j) return0if (i == j) return1if (dp[i][j][k] != -1) return dp[i][j][k]
// Skip either left or right character
var ans = maxOf(solve(i + 1, j, k, s), solve(i, j - 1, k, s))
// Calculate cost to match characters at positions i and j
val cost = minOf(kotlin.math.abs(s[i].code - s[j].code),
26 - kotlin.math.abs(s[i].code - s[j].code))
// If we can afford the cost, try matching the pair
if (k >= cost) {
ans = maxOf(ans, 2 + solve(i + 1, j - 1, k - cost, s))
}
dp[i][j][k] = ans
return ans
}
funlongestPalindromicSubsequence(s: String, k: Int): Int {
val n = s.length
dp = Array(n) { Array(n) { Array(k + 1) { -1 } } }
return solve(0, n - 1, k, s)
}
}
classSolution:
deflongestPalindromicSubsequence(self, s: str, k: int) -> int:
n = len(s)
dp = {}
defsolve(i: int, j: int, k: int) -> int:
if i > j:
return0if i == j:
return1if (i, j, k) in dp:
return dp[(i, j, k)]
# Skip either left or right character ans = max(solve(i +1, j, k), solve(i, j -1, k))
# Calculate cost to match characters at positions i and j cost = min(abs(ord(s[i]) - ord(s[j])), 26- abs(ord(s[i]) - ord(s[j])))
# If we can afford the cost, try matching the pairif k >= cost:
ans = max(ans, 2+ solve(i +1, j -1, k - cost))
dp[(i, j, k)] = ans
return ans
return solve(0, n -1, k)
use std::collections::HashMap;
impl Solution {
pubfnlongest_palindromic_subsequence(s: String, k: i32) -> i32 {
let chars: Vec<char>= s.chars().collect();
let n = chars.len();
letmut dp = HashMap::new();
fnsolve(
i: usize, j: usize, k: i32, chars: &[char],
dp: &mut HashMap<(usize, usize, i32), i32> ) -> i32 {
if i > j {
return0;
}
if i == j {
return1;
}
iflet Some(&cached) = dp.get(&(i, j, k)) {
return cached;
}
// Skip either left or right character
letmut ans = solve(i +1, j, k, chars, dp).max(solve(i, j -1, k, chars, dp));
// Calculate cost to match characters at positions i and j
let diff = (chars[i] asi32- chars[j] asi32).abs();
let cost = diff.min(26- diff);
// If we can afford the cost, try matching the pair
if k >= cost {
ans = ans.max(2+ solve(i +1, j -1, k - cost, chars, dp));
}
dp.insert((i, j, k), ans);
ans
}
solve(0, n -1, k, &chars, &mut dp)
}
}
functionlongestPalindromicSubsequence(s: string, k: number):number {
constn=s.length;
constdp=newMap<string, number>();
functionsolve(i: number, j: number, k: number):number {
if (i>j) return0;
if (i===j) return1;
constkey=`${i},${j},${k}`;
if (dp.has(key)) returndp.get(key)!;
// Skip either left or right character
letans= Math.max(solve(i+1, j, k), solve(i, j-1, k));
// Calculate cost to match characters at positions i and j
constdiff= Math.abs(s.charCodeAt(i) -s.charCodeAt(j));
constcost= Math.min(diff, 26-diff);
// If we can afford the cost, try matching the pair
if (k>=cost) {
ans= Math.max(ans, 2+solve(i+1, j-1, k-cost));
}
dp.set(key, ans);
returnans;
}
returnsolve(0, n-1, k);
}
Instead of using recursion with memoization, we can build the solution iteratively from smaller subproblems to larger ones. We fill the DP table in a specific order to ensure that when we compute dp[i][j][op], all the required subproblems have already been computed.
classSolution {
public:int longestPalindromicSubsequence(string s, int k) {
int n = s.size();
vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k +1, 0)));
// Base case: single characters
for (int i =0; i < n; i++) {
for (int op =0; op <= k; op++) {
dp[i][i][op] =1;
}
}
// Fill DP table for increasing substring lengths
for (int len =2; len <= n; len++) {
for (int i =0; i <= n - len; i++) {
int j = i + len -1;
for (int op =0; op <= k; op++) {
// Skip characters
dp[i][j][op] = max(dp[i +1][j][op], dp[i][j -1][op]);
// Try to match characters at i and j
int cost = min(abs(s[i] - s[j]), 26- abs(s[i] - s[j]));
if (op >= cost) {
dp[i][j][op] = max(dp[i][j][op], 2+ dp[i +1][j -1][op - cost]);
}
}
}
}
// Find maximum result
int result =0;
for (int op =0; op <= k; op++) {
result = max(result, dp[0][n -1][op]);
}
return result;
}
};
classSolution:
deflongestPalindromicSubsequence(self, s: str, k: int) -> int:
n = len(s)
dp = [[[0] * (k +1) for _ in range(n)] for _ in range(n)]
# Base case: single charactersfor i in range(n):
for op in range(k +1):
dp[i][i][op] =1# Fill DP table for increasing substring lengthsfor length in range(2, n +1):
for i in range(n - length +1):
j = i + length -1for op in range(k +1):
# Skip characters dp[i][j][op] = max(dp[i +1][j][op], dp[i][j -1][op])
# Try to match characters at i and j cost = min(abs(ord(s[i]) - ord(s[j])), 26- abs(ord(s[i]) - ord(s[j])))
if op >= cost:
dp[i][j][op] = max(dp[i][j][op], 2+ dp[i +1][j -1][op - cost])
# Find maximum resultreturn max(dp[0][n -1][op] for op in range(k +1))