Number of Distinct Substrings
Solve this Problems, count how many distinct (non-empty) substrings it has.
Every substring is a prefix of some suffix — specifically, the suffix that starts at the same position. So building a trie out of every suffix of s, one after another, means every distinct substring gets a node somewhere in that trie, and the trie's own structure prevents any duplicate from getting a second node: two suffixes that happen to share a prefix walk through the exact same existing nodes for as long as they agree. Counting how many nodes actually get freshly created — rather than reused — across all n suffix insertions gives the number of distinct substrings directly, without ever having to build a substring string, hash it, or check a set for membership.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ s.length ≤ 200 - ◆
s consists of lowercase English letters
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Hash Set of Every Substring
BruteGenerate every substring — every (start, end) pair — and drop each one into a hash set; duplicates collapse automatically, so the final set size is the answer. There are O(n²) substrings, and materializing plus hashing each one costs up to O(n) more, giving O(n³) overall.
O(n³)O(n²)1class Solution {
2 public int countDistinctSubstrings(String s) {
3 Set<String> substrings = new HashSet<>();
4 int n = s.length();
5 for (int i = 0; i < n; i++) {
6 for (int j = i + 1; j <= n; j++) {
7 substrings.add(s.substring(i, j));
8 }
9 }
10 return substrings.size();
11 }
12}Optimal — Trie of Every Suffix
OptimalEvery substring of s is a prefix of exactly one suffix of s — the suffix that starts where the substring starts. So insert all n suffixes into one shared trie, one character at a time, and count how many brand-new nodes get created along the way. A node is only created the first time some character sequence is seen; since the trie merges identical prefixes regardless of which suffix introduced them, every distinct substring produces exactly one new node, counted exactly once — no substring ever gets materialized or hashed.
O(n²)O(n²)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 }
5
6 public int countDistinctSubstrings(String s) {
7 TrieNode root = new TrieNode();
8 int count = 0;
9 int n = s.length();
10 for (int i = 0; i < n; i++) {
11 TrieNode node = root;
12 for (int j = i; j < n; j++) {
13 int idx = s.charAt(j) - 'a';
14 if (node.children[idx] == null) {
15 node.children[idx] = new TrieNode();
16 count++;
17 }
18 node = node.children[idx];
19 }
20 }
21 return count;
22 }
23}