Substrings and Frequency

Approach 

Brute Force Approach

The naive approach to solving the above problem is to generate all the substrings of string ‘S’ and count the frequency of each string formed. After storing the frequency of all the substrings in the map, count the number of strings whose frequency is greater than or equal to ‘F’ by traversing the map. This is the simplest but not the most efficient approach to solve the above problem. 

Time Complexity

O( N ^ 2), where ‘N’ is the length of the given string. Because generating all the substrings takes O(N ^ 2). 

Space Complexity

O(N ^ 2), where ‘N’ is the length of the string. Because storing all the strings in the map takes O(N ^ 2) extra space.

Suffix Array Approach

The above problem can be solved using the suffix array approach. We need to construct a suffix array ‘SA’ of the string ‘S’ in this approach. Create an array ‘LCP’ where LCP[i] = lcp(SA[i], SA[i+1]) where lcp is the longest common prefix.

The ‘LCP’ array can be seen as a histogram with each bar having height ‘LCP[i]’. Then for some range [i,j] if minimum of [LCP[i], LCP[i+1]… LCP[j]] is ‘M’, then it means a substring of length ‘M’, which is present at j-i+2 indices in string ‘S’.

Using this property, we can find the solution in the following way. Let ‘D[i]’ represent the number of substrings that repeat exactly ‘i’ times. If we can compute the array ‘D’, we can easily answer all the queries. For a given frequency F, required answer will be D[F] + D[F+1] + … D[length of S].

For a bar of height H (LCP[i] = H), let us assume that we know the largest interval (L[i], R[i]) such that the minimum of LCP array over the interval is equal to H, then it means that we have got a substring of length H, which repeats exactly R[i]-L[i]+2 times. 

We will update the ‘D’ array accordingly.

Pseudo Code

for V = 0 to N:
    sz = P[val].size()
    /* right is maintained for implementing two-pointer method.*/
    right = 0;
    for j = 0 to sz:
        index = P[val][j]
        /* to take care of the issue 2, don't overcount, always check whether your current element under*/
        /* consideration is not inside the range which has already been considered.*/
        if (index >= right):
            lo = L[index], hi = R[index]
            /* len denotes the current number of prefixes of the suffix corresponding to size V. */
            len = V;
            /* to take care of the issue 1.*/
            if (hi is defined, ie 0 <= hi < LCP.size()):
                len = min(len, val - LCP[hi])
            if (lo is defined, ie 0 <= lo < LCP.size()):
                len = min(len, val - LCP[hi]);
            /* add the current prefixes */
            D[hi-lo+2] += len * (hi - lo + 2);
       
            /* update the right pointer */
            right = index + 1;

You can also try this code with Online C++ Compiler

Run Code

Time Complexity

O(N), where ‘N’ is the length of the given string. Because storing all the suffix takes O(N). 

Space Complexity

O(N), where ‘N’ is the length of the string. Because storing all the suffix of string in the array takes O(N) extra space.

Also check out - Substr C++, and Euclid GCD Algorithm

FAQs

1. What is string hashing?
   String hashing is the best approach to change over a string into a whole number known as a hash of that string.
    
2. What are the advantages of Suffix Tree over Tries?
   Suffix Trees consume lesser space, and when you are storing a vast text, the difference between linear and quadratic space complexity can be huge. Suffix tree use can also reduce lookup time.
    
3. What are the similarities between the suffix tree and the generalized suffix tree?
   Both suffix trees and generalized suffix trees are implemented using a tree data structure, and both are used to perform operations in the suffix of the string.
    
4. What are the differences between the suffix tree and the generalized one? 
   The suffix tree is made only for a single string, whereas the generalized suffix tree is used for more than one string.
    
5. What are the applications of the Suffix Tree?
   While there are many applications of this data structure, the fundamental ones are searching a string in a Text in O(len(string)) time for multiple checks, searching for longest repeated string, longest common substring, etc. It's also used for searching patterns in DNA or protein sequences.

Key Takeaways

In this blog, we learned about an interesting problem based on a string. We solved the problem efficiently using the Combinatorics approach. Another problem involving substring is: here.

Check out this problem - Longest Common Prefix

Hence learning never stops, and there is a lot more to learn.
So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!