Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
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
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}


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!

Previous article
Largest Area
Next article
Queuing Problem
Live masterclass