LeetCode 3472: Longest Palindromic Subsequence After at Most K Operations Solution

Master LeetCode problem 3472 (Longest Palindromic Subsequence After at Most K Operations), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3472. Longest Palindromic Subsequence After at Most K Operations

Medium

String Dynamic Programming

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We can create a 3-dimensional DP array where dp[i][j][k] represents the length of the longest palindromic subsequence we can obtain by processing the subarray s[i...j] with at most k operations.

We can initialize the base cases where dp[i][i][k] = 1 since a single character is a palindrome, and dp[i][j][0] = length of longest palindromic subsequence of s[i...j] without any operations.

Then, we can iteratively fill in the DP array for increasing values of k. At each step, we consider two cases:

If s[i] == s[j], we update dp[i][j][k] by adding 2 to the length of the longest palindromic subsequence of s[i+1...j-1] with at most k operations.
Otherwise, we update dp[i][j][k] by considering the maximum of:
- dp[i+1][j][k-1] (performing an operation on s[i])
- dp[i][j-1][k-1] (performing an operation on s[j])
- dp[i+1][j-1][k-1] (performing an operation on both s[i] and s[j])

The final answer will be stored in dp[0][n-1][k], where n is the length of string s.

Solution Code

class Solution {
    public int longestPalindromeSubseq(String s, int k) {
        int n = s.length();
        int[][][] dp = new int[n][n][k+1];
        
        for (int i = 0; i < n; i++) {
            dp[i][i][0] = 1;
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j][0] = Math.max(dp[i+1][j][0], dp[i][j-1][0]);
                for (int kk = 1; kk <= k; kk++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j][kk] = dp[i+1][j-1][kk-1] + 2;
                    } else {
                        dp[i][j][kk] = Math.max(dp[i+1][j][kk-1], Math.max(dp[i][j-1][kk-1], dp[i+1][j-1][kk-1]));
                    }
                }
            }
        }
        
        return dp[0][n-1][k];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3472 (Longest Palindromic Subsequence After at Most K Operations)?

This page provides optimized solutions for LeetCode problem 3472 (Longest Palindromic Subsequence After at Most K Operations) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3472 (Longest Palindromic Subsequence After at Most K Operations)?

The time complexity for LeetCode 3472 (Longest Palindromic Subsequence After at Most K Operations) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3472 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3472 in Java, C++, or Python.

Back to LeetCode Solutions