Given a string s, count the number of distinct non-empty substrings of s.
Input: "abab" → Output: 7 (a, b, ab, ba, aba, bab, abab)Input: "aaa" → Output: 3 (a, aa, aaa)
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.
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)