Longest Palindromic Subsequence After at Most K Operations Solution
Longest Palindromic Subsequence After at Most K Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Palindromic Subsequence After at Most K Operations is a medium coding problem on strings and dynamic programming, asked in Google interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of lowercase letters and an integer k.
In one operation you may replace any character of s with the next or the previous letter of the alphabet, which wraps around: the letter after 'z' is 'a', and the letter before 'a' is 'z'.
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 = 2
Output: 3
Explanation: Change 'c' to 'd' (1 operation): "abded" contains the palindrome "ded".
Example 2
Input: s = "aaazzz", k = 4
Output: 6
Explanation: Turn each 'a' into 'z' (1 operation each, wrapping backwards) — after 3 operations the whole string is "zzzzzz".
Example 3
Input: s = "a", k = 1
Output: 1
Constraints
1 <= s.length <= 2001 <= k <= 200s consists only of lowercase English letters
Hints for Longest Palindromic Subsequence After at Most K Operations
Hint 1
Making two characters equal costs
min(|a - b|, 26 - |a - b|)operations — move one of them around the shorter side of the alphabet circle.Hint 2
Extend the classic longest-palindromic-subsequence interval DP with the budget:
dp[i][j][c]= longest palindrome insides[i..j]using at mostcoperations.Hint 3
dp[i][j][c] = max(dp[i + 1][j][c], dp[i][j - 1][c], 2 + dp[i + 1][j - 1][c - cost(s[i], s[j])]), the last only when the cost fits.
How to solve Longest Palindromic Subsequence After at Most K Operations
A palindromic subsequence pairs characters from the outside in, and each pair costs the circular distance between its letters. That is the standard interval DP for the longest palindromic subsequence with one extra dimension: the operations still available.
Approach
- Let
cost(a, b) = min(|a - b|, 26 - |a - b|). dp[i][i][c] = 1for everyc; an empty range is 0.- For
ifromn - 1down to 0 andj > i:dp[i][j][c] = max(dp[i + 1][j][c], dp[i][j - 1][c]), and ifcost(s[i], s[j]) <= c, also2 + dp[i + 1][j - 1][c - cost]. - Return
dp[0][n - 1][k].
Why it works
In an optimal palindrome inside s[i..j], either s[i] or s[j] is unused (drop it) or both are used — then they must be the outermost pair, made equal at minimum cost cost(s[i], s[j]), and the rest is an optimal palindrome of s[i+1..j-1] with the remaining budget. A middle character costs nothing because it does not need a partner.
Complexity
- Time —
O(n^2 · k) - Space —
O(n^2 · k)
Pitfalls
- The alphabet wraps: 'a' and 'z' are one operation apart, not 25.
- Only one character of a pair needs to change, so the pair costs the distance, not twice the distance.
- Budgets are "at most", so
dp[...][c]must be non-decreasing inc— which the recurrence gives automatically.
Reference solution
Python
def longestPalindromicSubsequence(s: str, k: int) -> int:
n = len(s)
a = [ord(ch) - 97 for ch in s]
K = k + 1
dp = [[None] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i] = [1] * K
for j in range(i + 1, n):
d = abs(a[i] - a[j])
cost = min(d, 26 - d)
left, right = dp[i + 1][j], dp[i][j - 1]
inner = dp[i + 1][j - 1] if i + 1 <= j - 1 else None
row = [0] * K
for c in range(K):
best = left[c] if left[c] > right[c] else right[c]
if cost <= c:
v = 2 + (inner[c - cost] if inner is not None else 0)
if v > best:
best = v
row[c] = best
dp[i][j] = row
return dp[0][n - 1][k]Java
public static int longestPalindromicSubsequence(String s, int k) {
int n = s.length(), K = k + 1;
int[][][] dp = new int[n][n][K];
for (int i = n - 1; i >= 0; i--) {
Arrays.fill(dp[i][i], 1);
for (int j = i + 1; j < n; j++) {
int d = Math.abs(s.charAt(i) - s.charAt(j));
int cost = Math.min(d, 26 - d);
for (int c = 0; c < K; c++) {
int best = Math.max(dp[i + 1][j][c], dp[i][j - 1][c]);
if (cost <= c) {
int inner = i + 1 <= j - 1 ? dp[i + 1][j - 1][c - cost] : 0;
best = Math.max(best, 2 + inner);
}
dp[i][j][c] = best;
}
}
}
return dp[0][n - 1][k];
}C++
int longestPalindromicSubsequence(string s, int k) {
int n = s.size(), K = k + 1;
vector<int> dp((size_t) n * n * K, 0);
auto at = [&](int i, int j, int c) { return ((size_t) i * n + j) * K + c; };
for (int i = n - 1; i >= 0; i--) {
for (int c = 0; c < K; c++) dp[at(i, i, c)] = 1;
for (int j = i + 1; j < n; j++) {
int d = abs(s[i] - s[j]);
int cost = min(d, 26 - d);
for (int c = 0; c < K; c++) {
int best = max(dp[at(i + 1, j, c)], dp[at(i, j - 1, c)]);
if (cost <= c) {
int inner = i + 1 <= j - 1 ? dp[at(i + 1, j - 1, c - cost)] : 0;
best = max(best, 2 + inner);
}
dp[at(i, j, c)] = best;
}
}
}
return dp[at(0, n - 1, k)];
}JavaScript
var longestPalindromicSubsequence = function(s, k) {
var n = s.length, K = k + 1;
var dp = new Array(n * n * K).fill(0);
var at = function(i, j, c) { return (i * n + j) * K + c; };
for (var i = n - 1; i >= 0; i--) {
for (var c0 = 0; c0 < K; c0++) dp[at(i, i, c0)] = 1;
for (var j = i + 1; j < n; j++) {
var d = Math.abs(s.charCodeAt(i) - s.charCodeAt(j));
var cost = Math.min(d, 26 - d);
for (var c = 0; c < K; c++) {
var best = Math.max(dp[at(i + 1, j, c)], dp[at(i, j - 1, c)]);
if (cost <= c) {
var inner = i + 1 <= j - 1 ? dp[at(i + 1, j - 1, c - cost)] : 0;
if (2 + inner > best) best = 2 + inner;
}
dp[at(i, j, c)] = best;
}
}
}
return dp[at(0, n - 1, k)];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming