Longest palindromic subsequence after at most k operations

impl Solution {
  pub fn longest_palindromic_subsequence(s: String, k: i32) -> i32 {
    let n = s.len();
    let b: Vec<i32> = s.bytes().map(|c| (c - b'a') as i32).collect();
    let k = k as i32;
    // dp[i][j] = max length of palindromic subsequence in s[i..=j] using at most some ops
    // Cost to pair s[i] and s[j]: min(|b[i]-b[j]|, 26-|b[i]-b[j]|)
    let cost = |i: usize, j: usize| -> i32 {
      let d = (b[i] - b[j]).abs();
      d.min(26 - d)
    };
    // dp[i][j][ops] would be too large. Use DP with ops as constraint.
    // dp[i][j] = min ops to make s[i..=j] a palindromic subsequence of length dp_len
    // Actually: dp[i][j] = max palindrome length in s[i..=j] using at most k ops.
    // But we can't use k as dimension if k is large.
    // Alternative: dp[i][j] = min ops to form longest palindrome of length L from s[i..=j].
    // Use: dp[i][j] = max len of pal subseq in s[i..=j] with total ops <= k.
    // This is equivalent to: dp2[i][j] where dp2[i][j][ops_used] = max length.
    // Since k can be up to 100*100 = 10000, dp with ops is expensive.
    // Better: dp[i][j] = min ops to pair chars and form palindrome of length L.
    // Classic approach: dp[i][j] = (max_length, min_ops_for_that_length).
    // Use: for each subproblem (i,j), compute a list of (len, min_ops) pairs.
    // Simpler: dp[i][j] = min ops to make s[i..=j] a palindrome of length j-i+1... no.
    // Efficient approach: for each pair (i,j) and target length l, dp[i][j][l] = min ops.
    // Then answer = max l such that dp[0][n-1][l] <= k.
    // n <= 200, l <= 200. O(n^2 * n) states with O(n) transition = O(n^4). Too slow for n=200?
    // O(n^3) DP: dp[i][j] = max palindrome length in s[i..=j] spending <= k ops.
    // For fixed k, this might work if we define dp[i][j] as a 1D value (not parameterized by k).
    // The key insight: a palindrome of length L needs L/2 pairs + (L%2==1 ? 1 center).
    // We want max L such that we can select L/2 non-overlapping disjoint pairs from s[i..=j]
    // using at most k ops total.
    // dp[i][j] = max (2*pairs + maybe_center) where sum of pair costs <= k.
    // For each pair (i,j), cost(i,j) = min distance between b[i] and b[j] in circular alphabet.
    // This is still complex. Let's use O(n^2 * k) DP:
    // ops[i][j] = min ops to make s[i..=j] a palindrome of len (j-i+1).
    // Then binary search... no.
    // Let's use: dp[i][j] = min ops to pair all n/2 chars optimally for a palindrome of max length.
    // Actually: for each pair of endpoints (i, j), dp[i][j] = min cost to form a palindrome starting with pairing i and j, then recursing.
    // dp[i][j] = cost(i,j) + dp[i+1][j-1]   if we pair i and j
    // dp[i][j] = min(dp[i+1][j], dp[i][j-1]) if we skip one
    // But this defines dp as "min cost for a full palindrome of length j-i+1", not variable length.
    // For the variable-length case:
    // dp[i][j] = vector of (length, min_cost) Pareto-optimal pairs.
    // This is tractable but complex.
    // Simplification: since k <= n*(n-1)/2 * 13 max (13 is max char dist), and n<=200:
    // dp[i][j] = array of size n+1 where dp[i][j][l] = min ops to get pal of length l from s[i..j].
    // n=200, O(n^3) states, each takes O(1) transition: total O(n^3) = 8*10^6. Feasible.
    let mut dp = vec![vec![vec![i32::MAX; n + 1]; n]; n];
    // Base: dp[i][i][1] = 0 (single char is palindrome of length 1, 0 ops).
    for i in 0..n { dp[i][i][1] = 0; }
    // dp[i][i+1][2] = cost(i,i+1): pair s[i] and s[i+1].
    // dp[i][i+1][0] = 0 (empty).
    for i in 0..n { dp[i][i][0] = 0; }
    for i in 0..n-1 { dp[i][i+1][0] = 0; dp[i][i+1][2] = cost(i, i+1); dp[i][i+1][1] = 0; }
    for len in 3..=n {
      for i in 0..=n-len {
        let j = i + len - 1;
        dp[i][j][0] = 0;
        // Option 1: skip s[i]
        for l in 0..=j-i { dp[i][j][l] = dp[i][j][l].min(dp[i+1][j][l]); }
        // Option 2: skip s[j]
        for l in 0..=j-i { dp[i][j][l] = dp[i][j][l].min(dp[i][j-1][l]); }
        // Option 3: pair s[i] and s[j]
        let c = cost(i, j);
        if dp[i+1][j-1].iter().copied().min().unwrap_or(i32::MAX) != i32::MAX {
          for l in 0..=len-2 {
            if dp[i+1][j-1][l] != i32::MAX {
              let new_cost = dp[i+1][j-1][l].saturating_add(c);
              dp[i][j][l+2] = dp[i][j][l+2].min(new_cost);
            }
          }
        }
      }
    }
    // Find max l such that dp[0][n-1][l] <= k
    let mut ans = 0;
    for l in 0..=n {
      if dp[0][n-1][l] <= k { ans = l as i32; }
    }
    ans
  }
}