Substring with largest variance

Hash Table String Dynamic Programming Enumeration

46.0% acceptance

Feb 25, 2026

1918

212

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same. Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s. A substring is a contiguous sequence of characters within a string.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn largest_variance(s: String) -> i32 {
    let bytes = s.as_bytes();
    // Find which chars are present
    let mut present = [false; 26];
    for &b in bytes { present[(b - b'a') as usize] = true; }

    let mut ans = 0;
    // For each ordered pair (major, minor), run Kadane's to find
    // max(count_major - count_minor) over all substrings with at least one minor
    for maj in 0..26u8 {
      if !present[maj as usize] { continue; }
      for min in 0..26u8 {
        if !present[min as usize] || maj == min { continue; }
        let (a, b) = (b'a' + maj, b'a' + min);
        // dp_no_b = max subarray sum (a=+1, b=-1) ending here (Kadane's)
        // dp_with_b = max such sum with at least one b
        let mut dp_no_b = 0i32;
        let mut dp_with_b = i32::MIN / 2;
        for &c in bytes {
          if c == b {
            // Including b: extend dp_with_b and dp_no_b, also dp_no_b can start dp_with_b
            dp_with_b = dp_with_b.max(dp_no_b).max(0) - 1;
            dp_no_b = dp_no_b.max(0) - 1;
          } else if c == a {
            dp_no_b = dp_no_b.max(0) + 1;
            dp_with_b += 1;
          }
          // else: other chars don't affect balance
          ans = ans.max(dp_with_b);
        }
      }
    }
    ans
  }
}