Count Distinct Substrings

Share

Given a string s, count the number of distinct non-empty substrings of s.

Example 1
Input: "abab" → Output: 7 (a, b, ab, ba, aba, bab, abab)
Example 2
Input: "aaa" → Output: 3 (a, aa, aaa)

Solution Approach

Build a Trie with all suffixes. Each new node created in the Trie corresponds to a new distinct substring.

  • Insert each suffix of s into the Trie.
  • Count nodes created (excluding root). Each new node represents one new distinct substring.
  • Return total new nodes.
Java
class Solution {
    public int countDistinct(String s) {
        // Use a Trie to count distinct substrings
        int[][] trie = new int[s.length() * s.length() + 1][26];
        int node = 1, count = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = 0;
            for (int j = i; j < s.length(); j++) {
                int c = s.charAt(j) - 'a';
                if (trie[cur][c] == 0) {
                    trie[cur][c] = node++;
                    count++;
                }
                cur = trie[cur][c];
            }
        }
        return count;
    }
}
  • Time Complexity: O(N^2)
  • Space Complexity: O(N^2)