Longest balanced substring ii

Hash Table String Prefix Sum

42.0% acceptance

Feb 24, 2026

555

134

You are given a string s consisting only of the characters 'a', 'b', and 'c'. A substring of s is called balanced if all distinct characters in the substring appear the same number of times. Return the length of the longest balanced substring of s.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn longest_balanced(s: String) -> i32 {
    let s: Vec<u8> = s.bytes().collect();
    let n = s.len();
    let mut best = 0i32;

    // Case 1: single-char runs (only a / only b / only c)
    {
      let mut run = 1i32;
      for i in 1..n {
        if s[i] == s[i - 1] {
          run += 1;
        } else {
          best = best.max(run);
          run = 1;
        }
      }
      if n > 0 { best = best.max(run); }
    }

    // Helper: within a char range, find max subarray where prefix diff repeats
    // diff: +1 for char_a, -1 for char_b
    fn max_equal_pair(s: &[u8], a: u8, b: u8) -> i32 {
      let mut best = 0i32;
      // split by the third character (anything that is neither a nor b)
      let mut seg_start = 0usize;
      let n = s.len();
      for i in 0..=n {
        if i == n || (s[i] != a && s[i] != b) {
          // segment [seg_start, i) contains only a and b
          let mut first_seen: HashMap<i32, i32> = HashMap::new();
          first_seen.insert(0, seg_start as i32 - 1);
          let mut diff = 0i32;
          for j in seg_start..i {
            if s[j] == a { diff += 1; } else { diff -= 1; }
            if let Some(&prev) = first_seen.get(&diff) {
              best = best.max(j as i32 - prev);
            } else {
              first_seen.insert(diff, j as i32);
            }
          }
          seg_start = i + 1;
        }
      }
      best
    }

    // Case 2: a and b equal, no c
    best = best.max(max_equal_pair(&s, b'a', b'b'));
    // Case 3: a and c equal, no b
    best = best.max(max_equal_pair(&s, b'a', b'c'));
    // Case 4: b and c equal, no a
    best = best.max(max_equal_pair(&s, b'b', b'c'));

    // Case 5: all three equal — use 2D prefix diff (ca-cb, ca-cc)
    {
      let mut first_seen: HashMap<(i32, i32), i32> = HashMap::new();
      first_seen.insert((0, 0), -1);
      let (mut ca, mut cb, mut cc) = (0i32, 0i32, 0i32);
      for i in 0..n {
        match s[i] { b'a' => ca += 1, b'b' => cb += 1, _ => cc += 1 }
        let key = (ca - cb, ca - cc);
        if let Some(&prev) = first_seen.get(&key) {
          best = best.max(i as i32 - prev);
        } else {
          first_seen.insert(key, i as i32);
        }
      }
    }

    best
  }
}