LeetCode 3472 - Longest Palindromic Subsequence After at Most K Operations

Here’s a complete, detailed technical solution guide for LeetCode 3472 following your formatting rules. The problem asks us to find the length of the longest palindromic subsequence in a string s after performing at most k operations.

leetcodemediumstringdynamic-programming

LeetCode Problem 3472

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming

Solution

Here’s a complete, detailed technical solution guide for LeetCode 3472 following your formatting rules.

Problem Understanding

The problem asks us to find the length of the longest palindromic subsequence in a string s after performing at most k operations. Each operation allows us to increment or decrement a character by one in the alphabet, with wraparound from 'a' to 'z' and vice versa.

The input s is a string of lowercase letters with length up to 200, and k is an integer up to 200 representing the maximum number of allowed character operations. The output is a single integer: the length of the longest palindromic subsequence achievable with these operations.

Essentially, the problem is a combination of palindromic subsequence dynamic programming and a limited edit-distance problem on individual characters. We are not required to output the subsequence itself, only its length.

Important edge cases include: when s is already a palindrome, when k is large enough to make any character change, or when s has only one character. Additionally, wraparound operations can be tricky for naive implementations, as changing 'a' to 'z' counts as one operation.

Approaches

Brute Force Approach

A brute-force approach would try every subsequence of s and, for each subsequence, check if it can be converted into a palindrome using at most k operations. This requires iterating over all subsequences (exponential in length), and for each, calculating the minimum operations needed to match corresponding characters from both ends.

Although correct in principle, this approach is exponentially slow for n = 200 because there are 2^n subsequences, making it infeasible.

Optimal Approach

The key insight is that we can use dynamic programming to compute the longest palindromic subsequence while simultaneously tracking the number of operations used.

We define a 3D DP array dp[i][j][k_used] representing the maximum palindromic subsequence length in the substring s[i..j] using at most k_used operations.

The recurrence relation is as follows:

  • If s[i] matches s[j], we can extend the palindrome without extra operations:

dp[i][j][k_used] = 2 + dp[i+1][j-1][k_used]

  • Otherwise, we can use operations to match them if k_used is sufficient:

Let cost = min_steps(s[i], s[j]) where min_steps calculates the minimum operations to make s[i] and s[j] equal considering alphabet wraparound. If k_used >= cost:

dp[i][j][k_used] = 2 + dp[i+1][j-1][k_used - cost]

  • We also consider skipping either end:

dp[i][j][k_used] = max(dp[i+1][j][k_used], dp[i][j-1][k_used])

This reduces the complexity from exponential to polynomial, manageable with constraints n, k <= 200.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n^2) Enumerates all subsequences and computes min operations for each
Optimal O(n^2 * k) O(n^2 * k) 3D DP tracking subsequence length for substrings and operation budget

Algorithm Walkthrough

  1. Initialize a 3D DP array dp[n][n][k+1] where n is the length of the string, filled with zeros. Each entry represents the maximum length of a palindromic subsequence for substring s[i..j] using at most k_used operations.
  2. Precompute a helper function min_steps(c1, c2) that calculates the minimum operations needed to convert character c1 to c2 with wraparound.
  3. Iterate over all possible substring lengths from 1 to n.
  4. For each substring s[i..j], iterate over all possible operation counts 0..k.
  5. If the substring has length 1, dp[i][i][k_used] = 1 since a single character is always a palindrome.
  6. For longer substrings, check if characters at both ends can be matched either directly or using k_used operations. Update dp[i][j][k_used] using the recurrence: either match both ends with or without operations, or skip one end.
  7. After filling the DP table, the answer is the maximum dp[0][n-1][k_used] for all 0 <= k_used <= k.

Why it works:

This approach ensures that for every substring and operation budget, we calculate the optimal palindromic subsequence length. By considering all substrings from shortest to longest, we guarantee that all subproblems are solved before using them in larger substrings, maintaining the DP invariant.

LeetCode 3472 - Longest Palindromic Subsequence After at Most K Operations

Problem Understanding

We are given a lowercase string s and an integer k.

A single operation allows us to move any character one step forward or one step backward in the cyclic alphabet. Because the alphabet wraps around, moving backward from 'a' produces 'z', and moving forward from 'z' produces 'a'.

The goal is not to transform the entire string into a palindrome. Instead, we want to find the longest palindromic subsequence that can exist after performing at most k operations anywhere in the string.

A subsequence is formed by deleting zero or more characters while preserving relative order. Therefore, we are free to skip characters that are not useful for building the palindrome.

The key observation is that when we choose two characters to become matching ends of a palindrome, we may spend some operations to make them equal. For characters a and b, the minimum number of operations required is the circular distance between them:

min(|a - b|, 26 - |a - b|)

For example:

'a' <-> 'c' : 2 operations
'a' <-> 'z' : 1 operation
'b' <-> 'y' : 3 operations

The constraints are:

1 <= n <= 200
1 <= k <= 200

Since both dimensions are relatively small, a dynamic programming solution with states involving both substring boundaries and remaining operations is feasible.

Important edge cases include:

  • A single-character string always has an LPS length of 1.
  • Two very different characters may still be matched cheaply because of alphabet wrapping.
  • The optimal solution may skip characters rather than spend operations on them.
  • Having many available operations does not necessarily mean the whole string becomes a palindrome, because subsequence ordering still matters.

Approaches

Brute Force

A brute-force solution would consider every possible subsequence, determine whether it can be converted into a palindrome within k operations, and keep the maximum length.

There are 2^n subsequences, making this approach completely infeasible for n = 200.

Even if we attempted to recursively explore all possible character transformations, the branching factor would explode. The search space is exponentially large and cannot be handled within the constraints.

Key Insight

The problem strongly resembles the classical Longest Palindromic Subsequence problem.

For a substring s[i...j], we have three choices:

  • Skip the left character.
  • Skip the right character.
  • Use both characters as matching ends of the palindrome.

The only new complication is that matching two characters may require operations.

If the cost to make s[i] and s[j] equal is c, and we still have at least c operations available, then we can take both characters and gain:

2 + LPS(i + 1, j - 1, remaining_budget - c)

This naturally leads to interval dynamic programming with an additional budget dimension.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Enumerates subsequences, completely infeasible
Optimal DP O(n²k) O(n²k) Interval DP with operation budget

Algorithm Walkthrough

Step 1: Define the matching cost

For two characters s[i] and s[j], compute:

diff = abs(ord(s[i]) - ord(s[j]))
cost = min(diff, 26 - diff)

This is the minimum number of operations needed to make the two characters equal.

Step 2: Define the DP state

Let:

dp[i][j][b]

represent the maximum palindromic subsequence length obtainable from substring:

s[i...j]

using at most b operations.

Step 3: Initialize base cases

A single character is always a palindrome of length 1.

Therefore:

dp[i][i][b] = 1

for every valid budget b.

An empty interval contributes length 0.

Step 4: Process substrings in increasing length

We compute answers for shorter intervals first so that larger intervals can reuse them.

For every interval (i, j):

  • Skip left character:
dp[i+1][j][b]
  • Skip right character:
dp[i][j-1][b]
  • Match both ends if budget allows:
2 + dp[i+1][j-1][b-cost]

Take the maximum of all valid choices.

Step 5: Return the final answer

The desired answer is:

dp[0][n-1][k]

which represents the entire string with at most k operations available.

Why it works

For every substring, any optimal palindromic subsequence must fall into one of three categories:

  • It does not use the left endpoint.
  • It does not use the right endpoint.
  • It uses both endpoints as matching palindrome characters.

The recurrence explicitly evaluates all three possibilities and chooses the best one. Since every smaller interval is solved optimally before being used, dynamic programming guarantees that the final result is optimal.

Python Solution

class Solution:
    def longestPalindromicSubsequence(self, s: str, k: int) -> int:
        n = len(s)
        
        def min_steps(c1: str, c2: str) -> int:
            diff = abs(ord(c1) - ord(c2))
            return min(diff, 26 - diff)
        
        dp = [[[0] * (k+1) for _ in range(n)] for _ in range(n)]
        
        for i in range(n):
            for k_used in range(k+1):
                dp[i][i][k_used] = 1
        
        for length in range(2, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                for k_used in range(k+1):
                    cost = min_steps(s[i], s[j])
                    if cost <= k_used:
                        dp[i][j][k_used] = max(dp[i][j][k_used], 2 + (dp[i+1][j-1][k_used-cost] if i+1 <= j-1 else 0))
                    dp[i][j][k_used] = max(dp[i][j][k_used], dp[i+1][j][k_used], dp[i][j-1][k_used])
        
        return max(dp[0][n-1])

Explanation:

We define min_steps to handle the wraparound cost between characters. The DP array dp[i][j][k_used] is filled using increasing substring lengths, and we try matching both ends or skipping either. The final answer is extracted as the maximum achievable palindrome length for the whole string with up to k operations. from array import array from typing import List

class Solution: def longestPalindromicSubsequence(self, s: str, k: int) -> int: n = len(s)

    dp = [[None] * n for _ in range(n)]

    for i in range(n):
        arr = array('H', [1] * (k + 1))
        dp[i][i] = arr

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            diff = abs(ord(s[i]) - ord(s[j]))
            cost = min(diff, 26 - diff)

            cur = array('H', [0] * (k + 1))

            left = dp[i + 1][j]
            right = dp[i][j - 1]

            middle = None
            if i + 1 <= j - 1:
                middle = dp[i + 1][j - 1]

            for budget in range(k + 1):
                best = left[budget]
                if right[budget] > best:
                    best = right[budget]

                if cost <= budget:
                    if length == 2:
                        candidate = 2
                    else:
                        candidate = 2 + middle[budget - cost]

                    if candidate > best:
                        best = candidate

                cur[budget] = best

            dp[i][j] = cur

    return dp[0][n - 1][k]


The implementation stores a budget array for every interval. Each entry `dp[i][j][b]` contains the best palindromic subsequence length obtainable from that interval using at most `b` operations.

Single-character intervals are initialized to `1`. We then process intervals in increasing order of length. For each interval and each budget, we evaluate the three recurrence options: skipping the left endpoint, skipping the right endpoint, or matching both endpoints after paying the required cost.

The answer for the full string is stored at `dp[0][n-1][k]`.

## Go Solution

```go
func longestPalindromicSubsequence(s string, k int) int {
    n := len(s)
    
    minSteps := func(c1, c2 byte) int {
        diff := int(c1 - c2)
        if diff < 0 {
            diff = -diff
        }
        if diff > 13 {
            diff = 26 - diff
        }
        return diff
    }
    
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, k+1)
        }
    }
    
    for i := 0; i < n; i++ {
        for kk := 0; kk <= k; kk++ {
            dp[i][i][kk] = 1
        }
    }
    
    for length := 2; length <= n; length++ {
        for i := 0; i <= n - length; i++ {
            j := i + length - 1
            for kk := 0; kk <= k; kk++ {
                cost := minSteps(s[i], s[j])
                if cost <= kk {
                    mid := 0
                    if i+1 <= j-1 {
                        mid = dp[i+1][j-1][kk-cost]
                    }
                    if 2 + mid > dp[i][j][kk] {
                        dp[i][j][kk] = 2 + mid
                    }
                }
                if dp[i+1][j][kk] > dp[i][j][kk] {
                    dp[i][j][kk] = dp[i+1][j][kk]
                }
                if dp[i][j-1][kk] > dp[i][j][kk] {
                    dp[i][j][kk] = dp[i][j-1][kk]
                }
            }
        }
    }
    
    res := 0
    for kk := 0; kk <= k; kk++ {
        if dp[0][n-1][kk] > res {
            res = dp[0][n-1][kk]
        }
    }
    return res
}

Go-specific notes:

We use slices to represent 3D arrays, taking care to initialize each layer. The minSteps function uses integer math to avoid negative differences. Otherwise, the logic mirrors the Python version.

Worked Examples

Example 1: s = "abced", k = 2

| i | j | k n := len(s)

dp := make([][][]int, n)
for i := 0; i < n; i++ {
	dp[i] = make([][]int, n)

	arr := make([]int, k+1)
	for b := 0; b <= k; b++ {
		arr[b] = 1
	}
	dp[i][i] = arr
}

for length := 2; length <= n; length++ {
	for i := 0; i+length-1 < n; i++ {
		j := i + length - 1

		diff := int(s[i]) - int(s[j])
		if diff < 0 {
			diff = -diff
		}

		cost := diff
		if 26-diff < cost {
			cost = 26 - diff
		}

		cur := make([]int, k+1)

		left := dp[i+1][j]
		right := dp[i][j-1]

		for budget := 0; budget <= k; budget++ {
			best := left[budget]
			if right[budget] > best {
				best = right[budget]
			}

			if cost <= budget {
				candidate := 2

				if length > 2 {
					candidate = 2 + dp[i+1][j-1][budget-cost]
				}

				if candidate > best {
					best = candidate
				}
			}

			cur[budget] = best
		}

		dp[i][j] = cur
	}
}

return dp[0][n-1][k]

}


The Go implementation follows the same state definition and recurrence. Since Go arrays are fixed-size, slices are used to store the budget dimension. Integer overflow is not a concern because the maximum answer is only `200`.

## Worked Examples

### Example 1

s = "abced" k = 2


Relevant pair costs:

| Pair | Cost |
| --- | --- |
| a,d | 3 |
| b,e | 3 |
| c,c | 0 |
| c,e | 2 |

Consider interval `"ced"`:

| Budget | Best Length |
| --- | --- |
| 0 | 1 |
| 1 | 1 |
| 2 | 3 |

With budget `2`, characters `'c'` and `'e'` can be matched by spending exactly `2` operations.

Eventually:

dp[0][4][2] = 3


Answer:

3


### Example 2

s = "aaazzz" k = 4


Cost between `'a'` and `'z'`:

1


The outermost pair can be matched for cost `1`.

The next outermost pair can also be matched for cost `1`.

The innermost pair can again be matched for cost `1`.

Total cost:

1 + 1 + 1 = 3


which is within the budget `4`.

DP therefore builds:

2 4 6


for increasing interval sizes.

Final answer:

6


## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n²k) | Every interval and budget value is processed once |
| Space | O(n²k) | DP stores a value for every interval and budget combination |

The string length and budget are both at most `200`, so the total number of states is:

200 × 200 × 201 ≈ 8 million


Each state is computed in constant time, giving an overall complexity of `O(n²k)`.

## Test Cases

sol = Solution()

assert sol.longestPalindromicSubsequence("abced", 2) == 3 # example 1 assert sol.longestPalindromicSubsequence("aaazzz", 4) == 6 # example 2

assert sol.longestPalindromicSubsequence("a", 1) == 1 # single character assert sol.longestPalindromicSubsequence("ab", 0) == 1 # no operations available assert sol.longestPalindromicSubsequence("az", 1) == 2 # wrap-around match

assert sol.longestPalindromicSubsequence("abc", 1) == 2 # one pair can be matched assert sol.longestPalindromicSubsequence("abcba", 0) == 5 # already palindrome assert sol.longestPalindromicSubsequence("abcd", 100) == 4 # enough budget for all pairs

assert sol.longestPalindromicSubsequence("zzzz", 0) == 4 # identical characters assert sol.longestPalindromicSubsequence("abcdef", 2) >= 2 # limited budget

assert sol.longestPalindromicSubsequence("abca", 1) == 4 # convert inner pair


### Test Summary

| Test | Why |
| --- | --- |
| `"abced", 2` | Official example |
| `"aaazzz", 4` | Official example |
| `"a", 1` | Minimum length string |
| `"ab", 0` | No operations available |
| `"az", 1` | Wrap-around distance |
| `"abc", 1` | Small nontrivial interval |
| `"abcba", 0` | Already a palindrome |
| `"abcd", 100` | Large budget |
| `"zzzz", 0` | Repeated characters |
| `"abcdef", 2` | Limited budget behavior |
| `"abca", 1` | Budget used on inner pair |

## Edge Cases

### Single Character String

When `n = 1`, the longest palindromic subsequence is always the character itself. A common bug is forgetting that a palindrome of length one is valid. The implementation initializes every `dp[i][i][b]` to `1`, guaranteeing correct behavior.

### Wrap-Around Transformations

Characters near opposite ends of the alphabet can sometimes be matched very cheaply. For example:

'a' <-> 'z'


requires only one operation, not twenty-five. The implementation always computes:

min(diff, 26 - diff)


which correctly handles the cyclic alphabet.

### Skipping Is Better Than Matching

Sometimes matching a pair consumes too much budget and prevents forming a longer palindrome elsewhere. A greedy strategy that always matches endpoints would fail. The DP recurrence explicitly considers both skip options:

dp[i+1][j] dp[i][j-1]


ensuring that the algorithm can ignore expensive characters when doing so leads to a better overall answer.

### Large Available Budget

Even when `k` is much larger than necessary, the answer cannot exceed `n`. The DP naturally respects subsequence structure and only counts valid palindrome constructions, preventing overcounting or invalid transformations.