Longest duplicate substring

String Binary Search Sliding Window Rolling Hash Suffix Array Hash Function

31.1% acceptance

Feb 25, 2026

2338

397

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap. Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_dup_substring(s: String) -> String {
    let bytes = s.as_bytes();
    let n = s.len();
    let modulus: u64 = 1_000_000_007;
    let base: u64 = 31;
    // binary search on length
    let check = |len: usize| -> Option<String> {
      if len == 0 { return Some(String::new()); }
      let mut pow = 1u64;
      for _ in 0..len-1 { pow = pow.wrapping_mul(base) % modulus; }
      let mut h: u64 = 0;
      for i in 0..len {
        h = (h.wrapping_mul(base) + bytes[i] as u64) % modulus;
      }
      let mut seen = std::collections::HashMap::new();
      seen.entry(h).or_insert_with(Vec::new).push(0usize);
      for i in 1..=(n-len) {
        h = (h + modulus - pow.wrapping_mul(bytes[i-1] as u64) % modulus) % modulus;
        h = (h.wrapping_mul(base) + bytes[i+len-1] as u64) % modulus;
        let positions = seen.entry(h).or_insert_with(Vec::new);
        for &prev in positions.iter() {
          if &bytes[prev..prev+len] == &bytes[i..i+len] {
            return Some(s[i..i+len].to_string());
          }
        }
        positions.push(i);
      }
      None
    };
    let (mut lo, mut hi) = (1usize, n - 1);
    let mut ans = String::new();
    while lo <= hi {
      let mid = lo + (hi - lo) / 2;
      if let Some(r) = check(mid) {
        ans = r;
        lo = mid + 1;
      } else {
        if mid == 0 { break; }
        hi = mid - 1;
      }
    }
    ans
  }
}