Number of Distinct Substrings in a String

111.1k
0

Given a string s, count how many distinct substrings it has. This count includes the empty substring "".

A substring means a continuous part of the string.

Example 1

Input: s = "ababa"

Output: 10

Explanation: The distinct substrings are "", "a", "b", "ab", "ba", "aba", "bab", "abab", "baba", and "ababa".

Example 2

Input: s = "aaa"

Output: 4

Explanation: The distinct substrings are "", "a", "aa", and "aaa".

Brute Force Approach

The first natural idea is to generate every possible substring and store it in a set.

A set is helpful because duplicate substrings are automatically ignored. So even if "a" appears many times, it will stay only once inside the set.

This approach is very easy to understand, and it is the best place to start. But it becomes slow because every substring is created as a brand-new string, and there are already O(N2) substrings before even thinking about duplicate handling.

Algorithm

  • Start with an empty hash set to store only unique substrings. This is needed because the same substring can appear from different positions.

  • Use one loop to choose the starting index of a substring, because every substring must begin somewhere.

  • Use another loop to choose the ending index, because once the start is fixed, many different substrings can grow from it.

  • Extract the substring from start to end and insert it into the set. This step is the heart of the brute force method because the set removes duplicates automatically.

  • After all substrings are processed, return the size of the set plus 1. The extra 1 is added because the empty substring is also counted in this problem.

Key Points

  • The empty substring is not generated by the loops, so it must be added separately in the final count.

Dry Run

Number of Distinct Substrings in a String Brute Dry Run

Number of Distinct Substrings in a String Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Counts distinct substrings by generating all substrings
and storing the unique ones in a hash set.
*/
int countDistinctSubstrings(string s) {
unordered_set<string> uniqueSubstrings;
for (int start = 0; start < (int)s.size(); start++) {
for (int end = start; end < (int)s.size(); end++) {
// Build the current substring so duplicate copies can be ignored by the set.
string currentSubstring = s.substr(start, end - start + 1);
uniqueSubstrings.insert(currentSubstring);
}
}
// Add one more count because the empty substring is also valid.
return (int)uniqueSubstrings.size() + 1;
}
};
// Driver code starts
int main() {
string s = "ababa";
Solution obj;
cout << obj.countDistinctSubstrings(s) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N3), because there are O(N2) substrings and creating each substring can take O(N) time in the worst case.

Space Complexity: O(N3) in the worst case, because many unique substrings can be stored and their total length can be large.

Better Approach

The brute force approach keeps storing full substring strings again and again.

But every substring is actually a prefix of some suffix. That small observation changes the whole direction. If all suffixes are inserted into a Trie, then every new Trie node represents a substring that has never appeared before. If a path already exists, that substring was already seen earlier. So instead of storing every substring directly, the Trie counts only the genuinely new ones.

Algorithm

  • Create a Trie root to store paths of substrings in shared form. This is useful because many substrings start with the same characters.

  • Start from every index of the string and treat it as the beginning of one suffix, because every substring is a prefix of some suffix.

  • Move forward character by character from that start index, because this builds all substrings that begin there.

  • For each character, check whether the current Trie node already has that child.

  • If the child does not exist, create it and increase the answer count. This is done because a newly created node means a brand-new substring has appeared for the first time.

  • Move to that child and continue growing the current suffix path.

  • After all suffixes are inserted, return the counted value plus 1. The extra 1 is needed for the empty substring.

Key Points

  • A newly created Trie node directly corresponds to one new distinct non-empty substring.

Dry Run

Number of Distinct Substrings in a String Better Dry Run

Number of Distinct Substrings in a String Better Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class TrieNode {
public:
vector<TrieNode*> children;
TrieNode() {
children.assign(26, nullptr);
}
};
class Solution {
public:
/*
Counts distinct substrings by inserting all suffix paths
into a trie and counting only newly created nodes.
*/
int countDistinctSubstrings(string s) {
TrieNode* root = new TrieNode();
// Count only non-empty distinct substrings while new trie nodes are created.
int distinctCount = 0;
for (int start = 0; start < (int)s.size(); start++) {
TrieNode* node = root;
for (int end = start; end < (int)s.size(); end++) {
int index = s[end] - 'a';
// A missing child means this substring has not appeared before.
if (node->children[index] == nullptr) {
node->children[index] = new TrieNode();
// Increase the count because a new trie node represents a new substring.
distinctCount++;
}
node = node->children[index];
}
}
// Add one more count because the empty substring is also valid.
return distinctCount + 1;
}
};
// Driver code starts
int main() {
string s = "ababa";
Solution obj;
cout << obj.countDistinctSubstrings(s) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), because all suffix paths together process O(N2)characters.

Space Complexity: O(N2), because in the worst case every substring path can create a new Trie node.

Optimal Approach

The Trie approach still stores every different substring path separately, so in the worst case it can grow to O(N2) size.

The next observation is more powerful: many substring paths behave in the same way for future extensions, so they can be merged into one state. That is exactly what a suffix automaton does. Each state represents a group of substrings with the same extension behavior. Because of this merging, the whole structure stays linear in size. The beautiful counting fact is that each state contributes a fixed number of new distinct substrings:

len(state) - len(link(state))

So once the automaton is built, the answer can be counted without listing every substring one by one.

Algorithm

  • Build the suffix automaton by reading the string from left to right, because the structure grows naturally when one new character is appended at a time.

  • For every new character, create a new state representing substrings that now end at this latest position.

  • Follow suffix links backward and add transitions for the new character where they are missing. This is needed so older suffixes also learn how to extend with the new character.

  • If a matching transition already exists in a correct form, connect the new state to that existing state through a suffix link, because no extra restructuring is needed.

  • Otherwise, create a clone state when the existing transition is too long. This clone is necessary to preserve the correct automaton structure without losing old paths.

  • After the automaton is built, visit every state except the initial state.

  • Add len(state) - len(link(state)) to the answer for each state, because this value tells exactly how many new distinct substrings that state contributes.

  • Add 1 at the end for the empty substring.

Dry Run

Number of Distinct Substrings in a String Optimal Dry Run

Number of Distinct Substrings in a String Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class State {
public:
// Stores the maximum substring length represented by this state.
int len;
// Points to the suffix link used to jump to a smaller related state.
int link;
// Stores transitions to the next states for different characters.
unordered_map<char, int> next;
State() {
len = 0;
link = -1;
}
};
class Solution {
private:
// Stores all states of the suffix automaton.
vector<State> states;
// Stores the index of the state for the full current string.
int last;
// Resets the suffix automaton to the initial empty state.
void initializeAutomaton() {
states.clear();
states.push_back(State());
last = 0;
}
// Adds one character to the suffix automaton while preserving correct links and transitions.
void extendAutomaton(char ch) {
// Create the new state for substrings ending with the current character.
int current = (int)states.size();
states.push_back(State());
// The new state represents substrings ending at the newest character.
states[current].len = states[last].len + 1;
// Start from the last full-string state and walk through suffix links.
int pointer = last;
// Add missing transitions so older suffixes can also extend with this character.
while (pointer != -1 && !states[pointer].next.count(ch)) {
states[pointer].next[ch] = current;
pointer = states[pointer].link;
}
// If no previous state can continue, the new state links back to the initial state.
if (pointer == -1) {
states[current].link = 0;
} else {
// Move to the next state that already has this character transition.
int nextState = states[pointer].next[ch];
// If the next state already has the correct length, its link can be reused directly.
if (states[pointer].len + 1 == states[nextState].len) {
states[current].link = nextState;
} else {
// Create a clone state to split paths that currently share too much.
int clone = (int)states.size();
states.push_back(states[nextState]);
// The clone keeps transitions but gets the shorter valid length boundary.
states[clone].len = states[pointer].len + 1;
// Redirect old transitions to the clone where the old path was too long.
while (pointer != -1 && states[pointer].next[ch] == nextState) {
states[pointer].next[ch] = clone;
pointer = states[pointer].link;
}
states[nextState].link = clone;
states[current].link = clone;
}
}
last = current;
}
public:
/*
Counts distinct substrings using a suffix automaton
and sums each state's new contribution.
*/
int countDistinctSubstrings(string s) {
initializeAutomaton();
for (char ch : s) {
extendAutomaton(ch);
}
long long distinctCount = 0;
for (int stateIndex = 1; stateIndex < (int)states.size(); stateIndex++) {
// Get the suffix link of the current state for contribution counting.
int suffixLink = states[stateIndex].link;
// This difference gives the number of new substrings contributed by this state.
distinctCount += states[stateIndex].len - states[suffixLink].len;
}
// Add one more count because the empty substring is also valid.
return (int)distinctCount + 1;
}
};
// Driver code starts
int main() {
string s = "ababa";
Solution obj;
cout << obj.countDistinctSubstrings(s) << endl;
return 0;

Complexity Analysis

Time Complexity: O(N), because a suffix automaton for one string is built in linear time.

Space Complexity: O(N), because the number of states and transitions grows linearly with the string length.

Interview follow-up Questions

Because the loops and structures naturally count only non-empty substrings. If the problem says the empty substring is valid, one extra count must be added at the end.

RecursionArraysTrieStringData Structures

Read Similar Blogs

HashingData Structures

Count Distinct Elements

Given an integer array arr[] , return the count of all distinct elements in the array. Input: arr = [10, 20, 20, 10, 30, 10] Output: 3 Explanation: The different values are 10 , 20 , and 30 . 10 an...

76.5k
Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67.1k
Comments0