Count the number of substrings of length M that appear exactly K times in a string

In this article, we will delve into a unique and fascinating problem in the field of computer science - "Count M-length substrings that occur exactly K times in a string". This type of question is often asked in programming competitions and interviews. Before we begin, let's define what we're dealing with -

• Substring− A contiguous sequence found in another string.

• M Length− The length of the substring we are interested in.

• K times − The exact number of times the substring should appear in the original string.

Algorithm description

To solve this problem, we will take advantage of the power of hash maps (also called unordered maps in C). Hash maps allow us to store data in the form of key-value pairs and provide constant time complexity for search and insertion operations, making it an excellent tool for solving such problems.

The algorithm for calculating the M-length substring that appears exactly K times in a string is as follows -

• Initialize an empty hash map.

• Iterate over the string and create all possible M-length substrings.

• For each substring, add it to the hash map. If it already exists, increase its count.

• After all substrings have been calculated, iterate over the hash map to find all substrings that occur exactly K times.

C implementation

This is the C implementation of the above algorithm -

Example

#include<bits/stdc++.h>
using namespace std;

int countSubstrings(string s, int M, int K) {
   unordered_map<string, int> count_map;
   int n = s.length();
   
   for (int i = 0; i <= n - M; i++) {
      string substring = s.substr(i, M);
      count_map[substring]++;
   }
   
   int count = 0;
   for (auto it : count_map) {
      if (it.second == K)
         count++;
   }

    return count;
}

int main() {
   string s = "abcabcabc";
   int M = 3;
   int K = 3;
   
   int result = countSubstrings(s, M, K);
   cout << "The number of M-length substrings occurring exactly K times is: " << result << endl;
   
   return 0;
}

Output

The number of M-length substrings occurring exactly K times is: 1

In the above code, the countSubstrings function takes the input string s, the length of the substring M and the number of occurrences K as parameters. It initializes an unordered map count_map to keep track of all substrings and their occurrences. It then iterates over the string to create all possible substrings of length M, and for each substring it increments the count in the map. Once all substrings have been computed, it iterates over the map to compute all substrings that occur exactly K times.

The main function is where code execution begins. It initializes the string s and the values ​​of M and K. Then call the countSubstrings function and print the result.

Test case example

Let us consider the string "abcabcabc" where M=3 and K=3.

Here, the M-length substrings are "abc", "bca", "cab", "abc", "bca", "cab", "abc". Obviously, the substring "abc" occurs exactly 3 times in the string, so the output of the program will be 1.

This approach to the problem, where we use a hash map to compute substrings, is a good example of the space-time trade-off in computer science. When we use extra space to store substrings and their counts, we can significantly reduce the time complexity of the problem by counting occurrences in constant time.

Time and space complexity

The time complexity of this algorithm is O(n), where n is the length of the string. This is because we iterate over the string only once to create all possible M length substrings.

Due to the storage requirements of the hash map, the space complexity is also O(n), in the worst case, each substring is unique, resulting in n different entries in the map.

in conclusion

In this article, we study a common problem in computer science - counting the number of M-length substrings that occur exactly K times in a string. We implemented an efficient solution in C using hash maps, which gave us constant time search and insertion operations. This problem is a perfect example of how data structures and algorithms can be used together to effectively solve complex problems.

The above is the detailed content of Count the number of substrings of length M that appear exactly K times in a string. For more information, please follow other related articles on the PHP Chinese website!