Find longest special substring that occurs thrice ii

Hash Table String Binary Search Sliding Window Counting

39.1% acceptance

Feb 25, 2026

406

You are given a string s that consists of lowercase English letters. A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special. Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice. A substring is a contiguous non-empty sequence of characters within a string.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

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

    // Compute runs for each char
    let mut runs: Vec<Vec<usize>> = vec![vec![]; 26];
    let mut i = 0;
    while i < n {
      let c = (bs[i] - b'a') as usize;
      let mut j = i;
      while j < n && bs[j] == bs[i] { j += 1; }
      runs[c].push(j - i);
      i = j;
    }

    let check = |k: usize| -> bool {
      for c in 0..26 {
        let total: usize = runs[c].iter().map(|&l| if l >= k { l - k + 1 } else { 0 }).sum();
        if total >= 3 { return true; }
      }
      false
    };

    if !check(1) { return -1; }
    let mut lo = 1usize;
    let mut hi = n;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if check(mid) { lo = mid; } else { hi = mid - 1; }
    }
    lo as i32
  }
}