Longest repeating substring

String Binary Search Dynamic Programming Rolling Hash Suffix Array Hash Function

63.4% acceptance

Mar 31, 2026

731

Given a string s, return the length of the longest repeating substrings. If no repeating substring exists, return 0.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_repeating_substring(s: String) -> i32 {
    let s = s.as_bytes();
    let n = s.len();
    // Binary search on length + HashSet check
    let check = |len: usize| -> bool {
      use std::collections::HashSet;
      let mut seen: HashSet<&[u8]> = HashSet::new();
      for i in 0..=n - len {
        let sub = &s[i..i + len];
        if !seen.insert(sub) {
          return true;
        }
      }
      false
    };
    let mut lo = 0i32;
    let mut hi = (n - 1) as i32;
    while lo < hi {
      let mid = lo + (hi - lo + 1) / 2;
      if check(mid as usize) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo
  }
}