Table of contents
1.
Introduction
2.
The Problem Statement
2.1.
Example
3.
Approach 
3.1.
Algorithm
3.2.
Program
3.3.
Output
3.4.
Time Complexity
3.5.
Space Complexity
4.
Key Takeaways
Last Updated: Mar 27, 2024

Length of Longest Substring Occurring in a Given Substring at Least ‘K’ Times

Author Ujjawal Gupta
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Ninja is very curious to know how to calculate the length of the longest substring in a given string which occurs at least ‘K’ times. Help ninja to write a program for same.

The above problem is the standard string traversal problem. String traversal based-coding problems are widely asked in coding contests and various coding interviews.

The Problem Statement

You are given an integer K’ and a string ‘S’ of length N’. Your task is to find the length of the longest substring of string ‘S,’ which occurs at least ‘K’ times in the given string ‘S.’  

Example

Let S = “ababak” and K = 2. Then all the substrings of the which occur at least two times are “a,” “b,” “ab,” “aba.” Out of these, the length of string “aba” is maximum, i.e., 3. Hence, the longest substring of string ‘S’ occurring at least two times is 3.

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!

Live masterclass