Longest almost palindromic substring

impl Solution {
  pub fn almost_palindromic(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len();

    // Precompute palindrome table: is_pal[i][j] = true if s[i..=j] is palindrome
    let mut is_pal = vec![vec![false; n]; n];
    for i in 0..n {
      is_pal[i][i] = true;
    }
    for i in 0..n-1 {
      is_pal[i][i+1] = s[i] == s[i+1];
    }
    for len in 3..=n {
      for i in 0..=n-len {
        let j = i + len - 1;
        is_pal[i][j] = s[i] == s[j] && is_pal[i+1][j-1];
      }
    }

    let mut ans = 2; // minimum: any 2-char substring, remove one char -> single char palindrome

    // For each substring s[i..=j] of length >= 2, check if removing one character makes it a palindrome
    // A substring of length L is almost-palindromic if:
    // - Removing the first char: s[i+1..=j] is palindrome
    // - Removing the last char: s[i..=j-1] is palindrome
    // - Or: match from both ends. When mismatch at positions l,r, check if
    //   removing s[l] (i.e., s[l+1..=r] is palindrome) or removing s[r] (i.e., s[l..=r-1] is palindrome)
    //   and the rest was already matched.
    //
    // More efficient approach: for each substring, try two-pointer from outside.
    // Match s[i]==s[j], move inward. On first mismatch at (l,r):
    //   - try skip l: check if s[l+1..=r] is palindrome -> whole thing is almost-palindromic
    //   - try skip r: check if s[l..=r-1] is palindrome -> whole thing is almost-palindromic
    // If no mismatch (already palindrome), we can remove the middle char (or any),
    //   so it's almost-palindromic if length >= 2 (removing one from palindrome of len >= 2
    //   gives palindrome of len >= 1, which is always a palindrome).
    //   Wait - removing one char from a palindrome doesn't always give a palindrome.
    //   E.g., "abba" remove 'a' -> "bba" not palindrome. Remove middle 'b' -> "aba" palindrome.
    //   So for a palindrome, we need to check if removing SOME character makes it a palindrome.
    //   For even palindrome "abba": remove index 1 -> "aba" palindrome. Yes.
    //   For odd palindrome "abcba": remove middle -> "abba" palindrome. Yes.
    //   Actually for any palindrome of length >= 2, removing the middle character (for odd)
    //   or either of the two middle characters (for even) always yields a palindrome.
    //   Proof: palindrome s[0..n-1]. For odd length, remove s[n/2]. Remaining is
    //   s[0..n/2-1] + s[n/2+1..n-1]. Since original is palindrome, s[i] = s[n-1-i].
    //   The remaining string has s[i] at position i for i < n/2, and s[n/2+1+j] = s[n-2-j]
    //   at position n/2 + j. We need remaining[i] = remaining[n-2-i].
    //   For i < n/2: remaining[i] = s[i], remaining[n-2-i]:
    //     if n-2-i >= n/2: remaining[n-2-i] = s[n-1-i] = s[i]. Palindrome holds.
    //   So yes, any palindrome of length >= 2 is almost-palindromic.

    for i in 0..n {
      for j in (i+1..n).rev() {
        let len = j - i + 1;
        if len <= ans as usize { break; }

        // Check if s[i..=j] is almost-palindromic
        let mut l = i;
        let mut r = j;
        let mut found_mismatch = false;
        let mut ok = false;

        while l < r {
          if s[l] == s[r] {
            l += 1;
            r -= 1;
          } else {
            found_mismatch = true;
            // Try removing s[l] or s[r]
            if is_pal[l+1][r] || is_pal[l][r-1] {
              ok = true;
            }
            break;
          }
        }

        if !found_mismatch {
          // It's a palindrome, and len >= 2, so it's almost-palindromic
          ok = true;
        }

        if ok {
          ans = ans.max(len as i32);
        }
      }
    }

    ans
  }
}