Number of distinct substrings in a string

String Trie Rolling Hash Suffix Array Hash Function

64.8% acceptance

Mar 31, 2026

208

No description available.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_distinct(s: String) -> i32 {
    // Trie-based approach for counting distinct substrings
    let b = s.as_bytes();
    let n = b.len();
    let mut trie = vec![[0u32; 26]]; // trie[node][char] = child node id
    let mut count = 0i32;
    for i in 0..n {
      let mut node = 0usize;
      for j in i..n {
        let c = (b[j] - b'a') as usize;
        if trie[node][c] == 0 {
          trie.push([0u32; 26]);
          trie[node][c] = (trie.len() - 1) as u32;
          count += 1;
        }
        node = trie[node][c] as usize;
      }
    }
    count
  }
}