Practice › Trie
Count Distinct Substrings
Medium · Trie · Asked at Amazon, Google, Microsoft
Print the number of distinct non-empty substrings of the string.
Input
A single lowercase string s.
Output
The number of distinct non-empty substrings.
Constraints
- 1 ≤ |s| ≤ 1000
Insert every suffix into a trie; each newly created node is a new distinct substring. That is O(n²) — much better than storing all substrings in a set.
Example 1
Input
abab
Output
7
Example 2
Input
aaa
Output
3
Hints
- Every substring is a prefix of some suffix.
- Insert all suffixes into a trie. Each node created corresponds to exactly one new distinct substring — count the nodes.
Approach
For every start index i, walk the trie with s[i..], creating a node whenever a letter is missing and counting it. A trie path equals one distinct substring, so the number of created nodes (excluding the root) is the answer. This is O(n²) time and nodes, versus O(n³) for putting substrings in a hash set. (Suffix arrays/automata do it in O(n log n) or O(n).)
Complexity: O(n²) time · O(n² ) nodes in the worst case
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
vector<array<int, 26>> t(1);
t[0].fill(-1);
long long count = 0;
for (int i = 0; i < n; i++) {
int cur = 0;
for (int j = i; j < n; j++) {
int c = s[j] - 'a';
if (t[cur][c] < 0) {
t[cur][c] = t.size();
t.emplace_back();
t.back().fill(-1);
count++;
}
cur = t[cur][c];
}
}
cout << count << "\n";
return 0;
}Python solution
s = input().strip()
root, count = {}, 0
for i in range(len(s)):
node = root
for c in s[i:]:
nxt = node.get(c)
if nxt is None:
nxt = node[c] = {}
count += 1
node = nxt
print(count)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
int n = s.length();
int maxNodes = n * (n + 1) / 2 + 1;
int[][] t = new int[maxNodes][];
t[0] = new int[26];
Arrays.fill(t[0], -1);
int size = 1;
long count = 0;
for (int i = 0; i < n; i++) {
int cur = 0;
for (int j = i; j < n; j++) {
int c = s.charAt(j) - 'a';
if (t[cur][c] < 0) {
t[size] = new int[26];
Arrays.fill(t[size], -1);
t[cur][c] = size++;
count++;
}
cur = t[cur][c];
}
}
System.out.println(count);
}
}Solve Count Distinct Substrings online · All practice problems