Intuition
We will discuss the brute force approach to solve the problem in this blog. In the brute force approach, we check for every possibility from which the answer can be obtained.
Approach
As mentioned above in the intuition section, the brute force approach is that we pick every possible substring and check if it is distinct. If it is a duplicate, we can simply discard the substring, and if it is unique and distinct, we can update the vector ‘cnt’ by increasing the count of distinct substrings starting from the first character of the current substring.
In this solution, all work has to be done to generate all the possible substrings. With the brute force approach, we can iterate through the string by moving to every index ‘i’ and then run a nested loop from the current index to the further indices ‘j’ and then consider the substring between index ‘i’ and ‘j’ to check if it's distinct. In this way, we can generate the resultant array ‘cnt’.
Below is the implementation of the above approach.
Implementation
// Program to find the number of distinct substrings.
#include <bits/stdc++.h>
using namespace std;
// Main Function.
int main()
{
// Input of main string.
string STR;
cin>>STR;
// Vector to store final result.
vector<int> cnt(26,0);
// Map to remember the unique substrings.
unordered_map<string, int> mp;
// Iterating through the string to generate substrings.
for(int i=0;i<STR.size();i++)
{
for(int j=i;j<STR.size();j++)
{
// Current substring.
string tmp = STR.substr(i,j-i+1);
// Marking the current substring.
mp[tmp]++;
// If the substring is distinct.
if(mp[tmp]==1)
cnt[tmp[0]-'a']++;
}
}
// Final output.
for(int i=0;i<26;i++)
cout<<cnt[i]<<" ";
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Input
aabbaa
Output
10 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Complexity Analysis
Time Complexity
O(N2), where ‘N’ is the size of string ‘STR’.
Explanation: The time complexity of the above algorithm can be calculated with the help of the most expensive operation, i.e., substrings generation. There are two nested loops running for N times; thus, the time complexity would be O(N X N), i.e., O(N2).
Space Complexity
O(N2), where ‘N’ is the size of string ‘STR’.
Explanation: The hash map we are using to store the occurrence of substrings contains the total number of substrings, i.e., N2. Thus the space complexity would be O(N2).
Also check out - Substr C++
FAQs
-
What is a string?
String is a type of array that stores characters. It is a contiguous sequence of characters stored in a connected manner, such that every character is linked to the previous and the next character.
-
What is the time complexity of the above algorithm?
The time complexity of the algorithm is O(N2), where ‘N’ is the size of the given string. This complexity is due to substring generation.
-
What is the space complexity of the above algorithm?
The space complexity of the above algorithm is O(N2), where ‘N’ is the size of the given string. This space is used by the hash map which we are using to store the substrings.
-
What is the size of the array which is used to store the number of substrings above?
The array ‘cnt’ is used to store the number of substrings, and its size is ‘26’, as we are having 26 lowercase letters.
-
What is the total number of substrings possible in a string of size ‘N’?
The total number of substrings possible in a string of size ‘N’ is (N * (N + 1)) / 2.
Key Takeaways
The above blog has covered an important and interesting problem related to Data Structures and Algorithms; and strings that help you enhance your problem-solving skills. It also helps us to generate all the possible substrings.
Check out this problem - Find Duplicate In Array
Find more such interesting questions on our practice platform Coding Ninjas Studio if you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!