Longest palindromic subsequence ii

impl Solution {
  pub fn longest_palindrome_subseq(s: String) -> i32 {
    let b = s.as_bytes();
    let n = b.len();
    // dp[i][j][last] = length of longest good palindromic subsequence in s[i..=j]
    // where 'last' is the last character used on the outer layer (0-25 for a-z, 26 for none)
    // A good palindromic subsequence: even length, palindrome, no two consecutive chars equal except middle two
    // Approach: dp[i][j][c] = longest good palindromic subseq in s[i..=j] where the outermost char is c
    let mut dp = vec![vec![vec![0i32; 27]; n]; n];
    // dp[i][j][c] = longest good palindromic subseq in s[i..=j] with outermost character c (0-25)
    // 26 means we haven't picked any character yet (the "overall" answer)
    
    // For length >= 2:
    // If b[i] == b[j] == c, and c != previous outer char:
    //   dp[i][j][c] = max over all c' != c of dp[i+1][j-1][c'] + 2
    //   Also dp[i][j][c] = 2 if i < j (base case: just the two chars)
    
    for len in 2..=n {
      for i in 0..=n - len {
        let j = i + len - 1;
        for c in 0..26u8 {
          // Try not including i or j with char c
          if i + 1 <= j {
            dp[i][j][c as usize] = dp[i][j][c as usize].max(dp[i + 1][j][c as usize]);
            dp[i][j][c as usize] = dp[i][j][c as usize].max(dp[i][j - 1][c as usize]);
          }
          // Try including both i and j if they match c
          if b[i] - b'a' == c && b[j] - b'a' == c && i < j {
            // The inner part must use a different outer char
            let mut best_inner = 0;
            for c2 in 0..26usize {
              if c2 != c as usize {
                best_inner = best_inner.max(dp[i + 1][j - 1][c2]);
              }
            }
            dp[i][j][c as usize] = dp[i][j][c as usize].max(best_inner + 2);
          }
        }
      }
    }
    
    let mut ans = 0;
    for c in 0..26 {
      ans = ans.max(dp[0][n - 1][c]);
    }
    ans
  }
}