Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Approach
4.1.
Implementation
4.2.
Complexity Analysis
4.2.1.
Time Complexity
4.2.2.
Space Complexity
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Ada String

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

String is one of the most important data structures in perspective to interviews in product-based companies. Advanced concepts related to strings such as suffix tree, Rabin-Karp, suffix arrays are also asked during interviews frequently. 
“Ada String” is one of such interesting problems related to strings, which would help us to understand strings in a better way. It also involves the use of substrings to a good extent.

substring is a contiguous sequence of characters in a string. 

Let us understand the problem with the help of the below problem statement.

Also read about, kth largest element in an array, and Euclid GCD Algorithm

Problem Statement

You are given a string STR of size N, consisting of lowercase letters. The task is to find an array storing number of distinct substrings starting with each letter.

Example

Input: STR = “aac”

Output: 4 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Explanation

  • Substrings starting with the letter ‘a’ are “a”, “aa”, “aac”, and “ac”, thus the first element of the output array is 4.
  • Substring starting with letter ‘c’ is “c” thus the third index of the output array is 1.
  • No other letter is present in the string STR, thus other indices are 0.
     

Input: STR = “ram”

Output: 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 3 0 0 0 0 0 0 0 0 

Explanation: Only three letters are present in the STR, ‘r’, ‘a’, and ‘m’:

  • Substrings starting from ‘r’ are “r”, “ra”, and “ram”, so 3.
  • Substrings starting from ‘a’ are “a” and “am”, so 2.
  • Substring starting from ‘m’ is “m” so 1.

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

  1. 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.  
     
  2. 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.
     
  3. 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. 
     
  4. 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.
     
  5. 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!

Live masterclass