Lexicographically smallest string after adjacent removals

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

    // can_remove[i][j] = true if substring s[i..=j] can be fully removed
    // A substring can be fully removed iff it can be partitioned into pairs of consecutive chars
    // DP: can_remove[i][j] = can_remove[i][k] && can_remove[k+1][j] for some k
    //     OR can_remove[i+1][j-1] && |b[i]-b[j]|==1 mod 26 (even length pairing from edges)
    let mut can_remove = vec![vec![false; n]; n];

    // Base: pairs
    for i in 0..n - 1 {
      let diff = (b[i] as i32 - b[i + 1] as i32).abs();
      if diff == 1 || diff == 25 {
        can_remove[i][i + 1] = true;
      }
    }

    // Fill for increasing lengths (even lengths only, since we remove pairs)
    // len2 = length of substring - 1 (so length = len2+1, even means len2 is odd)
    for len2 in (1..n).step_by(2) {
      for i in 0..n - len2 {
        let j = i + len2;
        // Option A: s[i] and s[j] are consecutive and can_remove[i+1][j-1]
        if len2 >= 1 {
          let diff = (b[i] as i32 - b[j] as i32).abs();
          if (diff == 1 || diff == 25) && (len2 < 2 || can_remove[i + 1][j - 1]) {
            can_remove[i][j] = true;
            continue;
          }
        }
        // Option B: split at any k with odd gap (both halves even length)
        let mut k = i + 1;
        while k < j {
          if can_remove[i][k] && can_remove[k + 1][j] {
            can_remove[i][j] = true;
            break;
          }
          k += 2;
        }
      }
    }

    // Now find lex smallest string by DP over which positions to keep
    // result[i] = lex smallest string achievable from suffix s[i..]
    // Try all subsets of removable intervals

    // dp[i] = lex smallest string using characters from position i onward
    // At position i: either keep s[i], or skip a removable segment [i..j] and recurse
    // dp[i] = min over:
    //   s[i] + dp[i+1]
    //   dp[j+1] for each j where can_remove[i][j]

    let mut dp: Vec<String> = vec![String::new(); n + 1];
    // dp[n] = ""
    for i in (0..n).rev() {
      // Option 1: keep s[i]
      let mut best = format!("{}{}", b[i] as char, &dp[i + 1]);
      // Option 2: skip a removable even-length segment [i..=j] starting at i
      // j-i must be odd so that length j-i+1 is even: j = i+1, i+3, i+5, ...
      let mut j = i + 1;
      while j < n {
        if can_remove[i][j] {
          let candidate = dp[j + 1].clone();
          if candidate < best {
            best = candidate;
          }
        }
        j += 2;
      }
      dp[i] = best;
    }

    dp[0].clone()
  }
}