Log inSign up
hardCoding NinjasNot Started

Count Distinct Substrings

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on Coding Ninjas
Lesson

Problem Statement

Given a string s of length n, find the total number of distinct substrings (including the empty string) of s.

A substring is a contiguous sequence of characters within a string. Two substrings are considered different if they differ in content or if they represent different character combinations.

Example 1 · Example 1: Short string with repeats:

Input: s = "abab"
Output: 8
Explanation: All distinct substrings are: "", "a", "b", "ab", "ba", "aba", "bab", "abab". Total = 8. Trie Structure of Suffixes: (root) / \ a b / \ b a / \ a b / b Distinct Trie nodes allocated = 7. Total distinct substrings = 1 + 7 = 8.

Example 2 · Example 2: All identical characters:

Input: s = "aaa"
Output: 4
Explanation: Distinct substrings are "", "a", "aa", "aaa". Total count = 4. Trie forms a single linear chain of 3 nodes: (root) -> a -> a -> a. Total = 1 + 3 = 4.

Constraints:

  • 1 <= s.length <= 1000
  • s consists only of lowercase English letters (a - z).

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the fundamental theorem: all substrings of s are prefixes of the suffixes of s.
  • Master Trie node allocation as an O(1) deduplication mechanism.
  • Analyze the difference between O(n3) string hashing and O(n2) Trie traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem asks for count of distinct substrings of a string.
  • String length is moderate (n <= 1000) where O(n2) time is permissible.
  • Need to deduplicate overlapping substrings without excessive string memory copying.

Algorithmic Decision Tree:

  • If n <= 1000: Insert all suffixes into a Trie in O(n2) time and O(n2 * 26) space.
  • If n <= 100: A hash set of substrings takes O(n3) time due to string copying/hashing overhead.
  • Each newly allocated node in the Trie directly corresponds to exactly one distinct substring.

Connected Patterns:

Suffix AutomatonSuffix TreeRabin-Karp Rolling Hash Set

1. Hash Set of Generated Substrings

Intuition

Iterate all pairs of (i, j) with 0 <= i <= j < n. Extract substring s[i..j] and insert into an unordered set. Return set.size() + 1.

When to apply: Quick sanity checks on small strings (n <= 100).

Algorithm

  1. Step 1: Initialize an empty unordered set of strings.
  2. Step 2: Loop i from 0 to n-1. Inner loop j from i to n-1.
  3. Step 3: Extract substring s.substr(i, j - i + 1) and insert into set.
  4. Step 4: Return set.size() + 1 (accounting for the empty string).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_set>
4using namespace std;
5
6class Solution {
7public:
8 int countDistinctSubstrings(string s) {
9 int n = s.length();
10 unordered_set<string> uniqueSubs;
11 for (int i = 0; i < n; i++) {
12 string current = "";
13 for (int j = i; j < n; j++) {
14 current += s[j];
15 uniqueSubs.insert(current);
16 }
17 }
18 return uniqueSubs.size() + 1; // +1 for empty string
19 }
20};
21
22int main() {
23 Solution sol;
24 string s = "abab";
25 cout << "Distinct substrings in \"" << s << "\": " << sol.countDistinctSubstrings(s) << endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n^3) — O(n2) substrings, each taking O(n) time to copy and compute hash.
  • Space complexity: O(n^3) — Set stores up to O(n2) substrings of length up to n.

Why Brute Force Doesn't Scale:

For n = 1000, n*(n+1)/2 ~ 500,000 substrings. Copying strings requires ~250MB and billions of CPU cycles, risking TLE.

Trie allocates pointers on the fly in O(1) without a single string allocation, finishing in under 30ms.

2. Rolling Hash (Polynomial Hash) Set

Intuition

For each starting position i, compute the polynomial hash incrementally as j advances from i to n-1: hash = (hash * P + s[j]) % M. Insert 64-bit hashes into a hash set.

When to apply: When memory is tight and strings cannot be stored directly.

Algorithm

  1. Step 1: Choose base P = 31 and large prime modulus M = 109 + 7 (or 64-bit unsigned overflow).
  2. Step 2: Loop i from 0 to n-1. Maintain hash = 0.
  3. Step 3: Inner loop j from i to n-1. Update hash = (hash * P + s[j]) % M. Insert hash into set.
  4. Step 4: Return set.size() + 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <unordered_set>
4using namespace std;
5
6class Solution {
7public:
8 int countDistinctSubstrings(string s) {
9 int n = s.length();
10 unordered_set<unsigned long long> hashSet;
11 const unsigned long long P = 131;
12
13 for (int i = 0; i < n; i++) {
14 unsigned long long currentHash = 0;
15 for (int j = i; j < n; j++) {
16 currentHash = currentHash * P + (s[j] - 'a' + 1);
17 hashSet.insert(currentHash);
18 }
19 }
20 return hashSet.size() + 1;
21 }
22};
23
24int main() {
25 Solution sol;
26 string s = "abab";
27 cout << "Distinct substrings (rolling hash): " << sol.countDistinctSubstrings(s) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(n^2) — Two nested loops each doing O(1) arithmetic and hash table insertion.
  • Space complexity: O(n^2) — Stores up to O(n2) integer hashes in the hash set.

3. Trie on Suffixes with In-Place Node Counter

Intuition

A Trie naturally deduplicates shared prefixes. Since every substring of s is a prefix of some suffix, inserting all n suffixes s[i..n-1] traverses the exact set of distinct substrings. Whenever a child pointer is null, allocate a new node and increment distinctCount by 1.

When to apply: Standard optimal solution for n <= 1000 without hash collision risk.

Algorithm

  1. Step 1: Define TrieNode with fixed array children[26] initialized to null.
  2. Step 2: Initialize distinctCount = 0 and create root node.
  3. Step 3: Loop i from 0 to n-1. Set curr = root.
  4. Step 4: Loop j from i to n-1. Let idx = s[j] - 'a'.
  5. Step 5: If curr->children[idx] == null, allocate new TrieNode, assign to child, and increment distinctCount++.
  6. Step 6: Move curr = curr->children[idx].
  7. Step 7: Return distinctCount + 1 (accounting for the empty string).

Interactive Trie Trace for Suffix Insertion

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Start at root for suffix s[0
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'a'
'a' (new)

Node order shown; add connections to display explicit tree edges.

curr: a
Check / comparison
child['a'] == null -> allocate new TrieNode
Decision / next transition
Create node 'a', count becomes 1.
Why this step matters

Step 1: Start at root for suffix s[0..1] = ab. Look up character a. Child is null, allocate node a. Distinct count = 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <vector>
4using namespace std;
5
6struct TrieNode {
7 TrieNode* children[26];
8 TrieNode() {
9 for (int i = 0; i < 26; i++) children[i] = nullptr;
10 }
11};
12
13class Solution {
14public:
15 int countDistinctSubstrings(string s) {
16 int n = s.length();
17 TrieNode* root = new TrieNode();
18 int count = 0;
19
20 for (int i = 0; i < n; i++) {
21 TrieNode* curr = root;
22 for (int j = i; j < n; j++) {
23 int idx = s[j] - 'a';
24 if (curr->children[idx] == nullptr) {
25 curr->children[idx] = new TrieNode();
26 count++;
27 }
28 curr = curr->children[idx];
29 }
30 }
31 return count + 1; // +1 for the empty string
32 }
33};
34
35int main() {
36 Solution sol;
37 string s = "abab";
38 cout << "Optimal Trie count for \"" << s << "\": " << sol.countDistinctSubstrings(s) << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(n^2) — Nested loops insert n suffixes of average length n/2 into the Trie. Each character check takes O(1) pointer lookup.
  • Space complexity: O(n^2 * 26) — In the worst case (all distinct characters), allocates O(n2) Trie nodes each with 26 pointers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Set of SubstringsO(n^3)O(n^3)Generate all n*(n+1)/2 substrings, push them into an unordered_set/hash set, return set.size() + 1.String copying and hash computation for O(n2) substrings of length up to n.
2.Better — Rolling Hash / Rabin-Karp Substring CountingO(n^2)O(n^2)Compute rolling polynomial hashes for all substrings and store 64-bit integer hashes in a hash set.Hash table bucket collisions and memory overhead of storing O(n2) hash integers.
3.Optimal — Trie Suffix InsertionOptimalO(n^2)O(n^2 * 26)Traverse every suffix starting at index i from 0 to n-1. Follow the Trie from root. Whenever a character branch does not exist, create it and increment count.None. Optimal for interview constraints n <= 1000.

Common Pitfalls & Crucial Edge Cases

Forgetting the empty string

The empty string is a valid substring of any string; forgetting + 1 is an instant fail.

Allocating strings during iteration

Building string copies inside nested loops degrades time from O(n2) to O(n3).

Memory leaks in C++

Failing to clean up allocated Trie nodes in long-running services.

Crucial Edge Cases to Validate:

  • Single character string ('a') — Exactly 2 distinct substrings: '' and a. Handled by 1 node allocation.
  • All characters identical ('aaaa') — Nodes form a straight chain of length n. Count = n + 1.
  • All distinct characters ('abcdef') — Every substring is unique. Total nodes created = n*(n+1)/2. Count = n*(n+1)/2 + 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the key mathematical equivalence immediately: 'Every substring of s is a prefix of some suffix of s.'
  2. Explain that a Trie inherently deduplicates prefixes, so every newly allocated node corresponds 1:1 to a novel substring.
  3. Mention that for massive strings (n >= 105), a Suffix Automaton or Suffix Array achieves O(n) or O(n log n) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the number of allocated Trie nodes equal the count of distinct non-empty substrings?

2.What is the optimal time complexity of the Trie approach for a string of length n?

Back to DSA Sheet