Longest Palindromic Subsequence After at Most K Operations Python/Java solution

Python and Java implementations typically use recursive DFS with a memoization cache such as functools.lru_cache in Python or a HashMap/3D array in Java. The algorithm tracks (left index, right index, remaining operations) and computes the best palindrome length in O(n^2 * k) time.

What is the best approach for Longest Palindromic Subsequence After at Most K Operations?

The best approach uses memoized search (top‑down dynamic programming). Define a DP state (i, j, k) representing the longest palindromic subsequence inside substring s[i..j] with k operations remaining. At each step you either match the characters (spending the required cost) or skip one side. This reduces repeated work and runs in O(n^2 * k) time.

Is Longest Palindromic Subsequence After at Most K Operations asked at Google/Amazon/Meta?

Palindrome subsequence problems and constrained dynamic programming variants frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact numbered problem may vary, the pattern of DP on substrings with extra constraints is a common interview topic.

What data structure is used in Longest Palindromic Subsequence After at Most K Operations?

The solution primarily uses dynamic programming with memoization. A 3D DP cache or hash map stores results for states defined by substring indices and remaining operations (i, j, k). Recursion or a top‑down DFS drives the state transitions.

What is the time complexity of Longest Palindromic Subsequence After at Most K Operations?

The optimized dynamic programming solution runs in O(n^2 * k) time. There are O(n^2) possible substring pairs (i, j) and up to k remaining operation states. Each state performs constant transitions such as matching characters or skipping one index.

Description Hints 3 Solution Video 18:52

3472. Longest Palindromic Subsequence After at Most K Operations

Q: Is Longest Palindromic Subsequence After at Most K Operations easy or hard?

The problem is generally rated Medium. The base idea resembles the classic longest palindromic subsequence DP, but the added constraint of at most k operations introduces an additional state dimension, increasing both reasoning complexity and implementation detail.

Q: How to solve Longest Palindromic Subsequence After at Most K Operations in O(n^2 * k)?

Use top‑down DP with memoization. Recursively evaluate dfs(i, j, remainingOps) and cache results. If characters match or can be converted within the remaining cost, include them in the palindrome and move inward; otherwise try skipping one side. Memoization ensures each (i, j, k) state is computed once.

Medium38.0% acceptance1 company

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.

Asked at 1 company

Google

Topics

Dynamic Programming String

Hints open one at a time

Hint 1

Use dynamic programming.

Hint 2

dp[i][j][k] is the length of the longest palindromic subsequence in substring [i..j] with cost at most k.

Hint 3

dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k], dp[i + 1][j - 1][k - dist(s[i], s[j])] + 2), where dist(x, y) is the minimum cyclic distance between x and y.

18:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestPalindromicSubsequence(self, s: str, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"abced"
2

Input

"aaazzz"
4

Your code is saved on this device.Solution