Longest Palindromic Subsequence After at Most K Operations

Medium
1676.

Longest Palindromic Subsequence After at Most K Operations

Longest Palindromic Subsequence After at Most K Operations is a medium coding problem on strings and dynamic programming, asked in Google interviews.

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 <= 200
  • 1 <= k <= 200
  • s consists only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestPalindromicSubsequence = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 200
  • 1 <= k <= 200
  • s consists only of lowercase English letters

Hints for Longest Palindromic Subsequence After at Most K Operations

  1. 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.

  2. Hint 2

    Extend the classic longest-palindromic-subsequence interval DP with the budget: dp[i][j][c] = longest palindrome inside s[i..j] using at most c operations.

  3. 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

  1. Let cost(a, b) = min(|a - b|, 26 - |a - b|).
  2. dp[i][i][c] = 1 for every c; an empty range is 0.
  3. For i from n - 1 down to 0 and j > i: dp[i][j][c] = max(dp[i + 1][j][c], dp[i][j - 1][c]), and if cost(s[i], s[j]) <= c, also 2 + dp[i + 1][j - 1][c - cost].
  4. 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 in c — 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