Longest Palindromic Subsequence After at Most K Operations - Solution & Explanation

Problem Overview: You are given a string s and an integer k. You may perform at most k character modification operations. Each operation changes a character toward another letter with a circular alphabet cost. The goal is to compute the maximum length of a palindromic subsequence that can be formed after spending at most k total cost.

The challenge combines classic string subsequence reasoning with a constrained operation budget. You must decide whether to match characters at both ends of a substring or skip them, while tracking how many operations remain.

Approach 1: Brute Force Recursion (Exponential Time)

The naive idea explores every subsequence while trying to match characters from both ends. For indices i and j, either skip the left character, skip the right character, or try converting them to match if the cost fits within the remaining budget. This produces a recursive branching tree where each state represents (i, j, remainingOps). Without caching, many identical subproblems repeat, leading to exponential time complexity O(3^n) in the worst case and recursion depth O(n) space. This approach mainly helps understand the decision process but is impractical for real constraints.

Approach 2: Memoized Search / Top‑Down Dynamic Programming (O(n^2 * k))

The optimal strategy uses dynamic programming with memoization. Define a recursive function dfs(i, j, rem) that returns the longest palindromic subsequence length within substring s[i..j] when rem operations remain. If characters already match, include both ends and continue with dfs(i+1, j-1, rem). If they differ, compute the circular alphabet cost to transform them into the same character; if that cost ≤ rem, match them and recurse with reduced operations.

You also consider skipping characters: dfs(i+1, j, rem) or dfs(i, j-1, rem). Memoization stores results for every (i, j, rem) state, eliminating repeated computation. The number of states is O(n^2 * k), and each state performs constant work, producing O(n^2 * k) time complexity and O(n^2 * k) space for the cache. This technique is a standard pattern in constrained subsequence problems that combine string processing with dynamic programming.

Recommended for interviews: Interviewers expect the memoized search or equivalent DP formulation. Starting with the recursive idea shows you understand subsequence choices (match or skip). Adding memoization demonstrates optimization skills and knowledge of overlapping subproblems, which is the key insight behind the O(n^2 * k) solution.