Approach
The above problem can be solved by generating all the substrings of string ‘S’ and storing the frequency of each substring in the hash map. Then, traverse the map and check whether the string's frequency is greater than or equal to ‘K.’ if it is, then checks whether that string's length is greater than the previous answer. If it is, then update the final answer.
The algorithm of the approach is discussed below.
Algorithm
-
Define a function ‘getLonggestSubstring()’:
-
Function Description:
- It takes string ‘S’ and an integer ‘K’ as a parameter.
- It returns the length of the longest substring, which occurs at least ‘K’ times in ‘S.’
-
Function Working:
- Create a hash map ‘MP’ to store the frequency of each string.
- Iterate loop from i = 0 to i < S.LENGTH():
- Create string ‘TEMP’.
- Iterate loop from j = i to j < S.LENGTH():
- TEMP += S[j].
- MP[TEMP]++.
- Create ANS = 0.
- Iterate ‘MP’ :
- If IT.SECOND > K :
- ANS = MAX (ANS , IT.FIRST.LENGTH()).
- Return ‘ANS’.
- Call the above function in the main function and pass ‘S’ and ‘K’.
Program
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// Define a function.
int getLongestSubstring(string &s, int k)
{
// Creating map to store the frequency of each string.
unordered_map<string, int> mp;
for (int i = 0; i < s.size(); i++)
{
// Temporary string to store the substring.
string temp;
for (int j = i; j < s.size(); j++)
{
temp += s[j];
// Storing frequency.
mp[temp]++;
}
}
// To store the answer.
int ans = 0;
// Iterate map.
for (auto it : mp)
{
if (it.second >= k)
{
// Update ans.
ans = max(ans, (int)it.first.size());
}
}
return ans;
}
int main()
{
// Taking 'N' and 'K' as an input.
int n, k;
cin >> n >> k;
// Taking string as an input.
string s;
cin >> s;
// Function Call.
int ans = getLongestSubstring(s, k);
cout << ans;
}

You can also try this code with Online C++ Compiler
Run Code
Input
6 2
ababak
Output
3
Time Complexity
O(N^2 ), where ‘N’ is the length of the given string. Generating each substring of a string takes O(N ^ 2) and inserting it in hash map takes O(1). Hence its total time complexity is O(N^2 ).
Space Complexity
O(N ^ 2), where ‘N’ is the length of the given string.
In the worst case, each substring is stored in the map which takes O(N ^ 2) space.
Also check out - Substr C++
Key Takeaways
In this blog, we have learned how to calculate the length of the longest substring which occurs at least ‘K’ times in the given string. We have discussed how to generate all the substrings of a string and how to store the frequency of string using map.
Recommended problems -
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!