3472. Longest Palindromic Subsequence After at Most K Operations

SourceWeekly Contest 439 Q2DifficultyMediumRating1883

Description

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 palindromic subsequence 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, 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.

Example 2:

Input: s = "aaazzz", k = 4

Output: 6

Explanation:

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.

Constraints:

1 <= s.length <= 200
1 <= k <= 200
s consists of only lowercase English letters.

Solutions

Solution 1: Memoized Search

Thinking

An operation moves a letter to an adjacent letter on the cycle, at most \(k\) times; we want the longest palindromic subsequence. Pairing the two ends costs the circular alphabet distance.

Classic LPS plus a remaining-budget dimension. State \((i,j,k)\) has size \(n^2(k+1)\) and memoizes well.

Transitions drop the left or right character, or spend \(t=\min(|s_i-s_j|,26-|s_i-s_j|)\) to pair them. Empty and singleton intervals are the base.

We design a function \(\textit{dfs}(i, j, k)\), which represents the length of the longest palindromic subsequence that can be obtained in the substring \(s[i..j]\) with at most \(k\) operations. The answer is \(\textit{dfs}(0, n - 1, k)\).

The calculation process of the function \(\textit{dfs}(i, j, k)\) is as follows:

If \(i > j\), return \(0\);
If \(i = j\), return \(1\);
Otherwise, we can ignore \(s[i]\) or \(s[j]\) and calculate \(\textit{dfs}(i + 1, j, k)\) and \(\textit{dfs}(i, j - 1, k)\) respectively; or we can change \(s[i]\) and \(s[j]\) to the same character and calculate \(\textit{dfs}(i + 1, j - 1, k - t) + 2\), where \(t\) is the ASCII code difference between \(s[i]\) and \(s[j]\).
Return the maximum value of the above three cases.

To avoid repeated calculations, we use memoized search.

The time complexity is \(O(n^2 \times k)\), and the space complexity is \(O(n^2 \times k)\). Where \(n\) is the length of the string \(s\).

Python3JavaC++GoTypeScript

class Solution:
    def longestPalindromicSubsequence(self, s: str, k: int) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i > j:
                return 0
            if i == j:
                return 1
            res = max(dfs(i + 1, j, k), dfs(i, j - 1, k))
            d = abs(s[i] - s[j])
            t = min(d, 26 - d)
            if t <= k:
                res = max(res, dfs(i + 1, j - 1, k - t) + 2)
            return res

        s = list(map(ord, s))
        n = len(s)
        ans = dfs(0, n - 1, k)
        dfs.cache_clear()
        return ans

class Solution {
    private char[] s;
    private Integer[][][] f;

    public int longestPalindromicSubsequence(String s, int k) {
        this.s = s.toCharArray();
        int n = s.length();
        f = new Integer[n][n][k + 1];
        return dfs(0, n - 1, k);
    }

    private int dfs(int i, int j, int k) {
        if (i > j) {
            return 0;
        }
        if (i == j) {
            return 1;
        }
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        int res = Math.max(dfs(i + 1, j, k), dfs(i, j - 1, k));
        int d = Math.abs(s[i] - s[j]);
        int t = Math.min(d, 26 - d);
        if (t <= k) {
            res = Math.max(res, 2 + dfs(i + 1, j - 1, k - t));
        }
        f[i][j][k] = res;
        return res;
    }
}

class Solution {
public:
    int longestPalindromicSubsequence(string s, int k) {
        int n = s.size();
        vector f(n, vector(n, vector<int>(k + 1, -1)));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
            if (i > j) {
                return 0;
            }
            if (i == j) {
                return 1;
            }
            if (f[i][j][k] != -1) {
                return f[i][j][k];
            }
            int res = max(dfs(i + 1, j, k), dfs(i, j - 1, k));
            int d = abs(s[i] - s[j]);
            int t = min(d, 26 - d);
            if (t <= k) {
                res = max(res, 2 + dfs(i + 1, j - 1, k - t));
            }
            return f[i][j][k] = res;
        };
        return dfs(0, n - 1, k);
    }
};

func longestPalindromicSubsequence(s string, k int) int {
    n := len(s)
    f := make([][][]int, n)
    for i := range f {
        f[i] = make([][]int, n)
        for j := range f[i] {
            f[i][j] = make([]int, k+1)
            for l := range f[i][j] {
                f[i][j][l] = -1
            }
        }
    }
    var dfs func(int, int, int) int
    dfs = func(i, j, k int) int {
        if i > j {
            return 0
        }
        if i == j {
            return 1
        }
        if f[i][j][k] != -1 {
            return f[i][j][k]
        }
        res := max(dfs(i+1, j, k), dfs(i, j-1, k))
        d := abs(int(s[i]) - int(s[j]))
        t := min(d, 26-d)
        if t <= k {
            res = max(res, 2+dfs(i+1, j-1, k-t))
        }
        f[i][j][k] = res
        return res
    }
    return dfs(0, n-1, k)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

function longestPalindromicSubsequence(s: string, k: number): number {
    const n = s.length;
    const sCodes = s.split('').map(c => c.charCodeAt(0));
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: n }, () => Array(k + 1).fill(-1)),
    );

    function dfs(i: number, j: number, k: number): number {
        if (i > j) {
            return 0;
        }
        if (i === j) {
            return 1;
        }

        if (f[i][j][k] !== -1) {
            return f[i][j][k];
        }

        let res = Math.max(dfs(i + 1, j, k), dfs(i, j - 1, k));
        const d = Math.abs(sCodes[i] - sCodes[j]);
        const t = Math.min(d, 26 - d);
        if (t <= k) {
            res = Math.max(res, 2 + dfs(i + 1, j - 1, k - t));
        }
        return (f[i][j][k] = res);
    }

    return dfs(0, n - 1, k);
}

3472. Longest Palindromic Subsequence After at Most K Operations

Description

Solutions

Solution 1: Memoized Search

Comments