 # Help in this question

given a string of lowercase alphabets A of size n and an integer x.

return the length of longest substring of a which is occuring atleast x times in a.

n is between 1 and 100.
also x is between 1 and 100

plz help.

1 Like

You can store the frequency of each substring in a map and then return the one greater than equal to x

Constraints for n are small so brute force should pass.

2 Likes

i have never used map.

will you please explain with code

thanks for helping

Ok ill post the code in 5 minutes

1 Like

provide the link of the question.
and yes it will be easy if you use
std::map, just read it on gfg.

this question was asked yesterday by my college coding club by my senior.

i wasnt able to do it

`int` `n = str.size();`

`unordered_map<string,` `int` `> m;`

`for` `(` `int` `i = 0; i < n; i++) {`

`string s =` `""` `;`

`for` `(` `int` `j = i; j < n; j++) {`

`s += str[j];`

`m[s]++;`

`}`

`}`

This part will store all substrings

Now we would want a substring occuring x number of times
Int maxm=0 ( to store the string with max frequency)
So traverse the map
Iterator. second has the frequency of substrings and since we want the longest length substrint occuring atleast x times , it can have maximum occurence , so just find the substring having maximum occurence and return it

If there is no such substring , return -1 i guess

2 Likes

Is this fine ? @noneoftheabove

you helped a lot but may u please provide whole code … I need to mail to my coding club

i will understand the code

input is “aaaaa”
x is 2
so output will be 4
as substring aaaa occurs twice in A
and there is no string longer than that

input is aaaaa
x is 6
so output wil be 0

You just have to traverse the map .
Declare an iterator or an auto element
And keep on updating maxm and the substring encountered.

This will be done in one loop

`string str;`

`for` `(` `auto` `it= m.begin(); it != m.end(); it++) {`

`if` `(it->second > maxm) {`

`maxm = it->second;`

`str= it->first;`

`}`

`else` `if` `(it->second == maxm) {`

`string newstr= it->first;`

`if` `(newstr.size() > str.size())`

`str = newstr`

`}`

`}`
`if(maxm>=x)` `return str.size()`
else return -1

So this part will return the length of the maximum occuring substring , and ive put a check for maxm>=x

2 Likes

Ok i am posting the code

1 Like

which is the final code…

You can try this code , but you can optimize it

# include<bits/stdc++.h>

using namespace std;

int main (){
string s;
map<string,int> track;
cin>>s;
int x;
cin>>x;
for(int i=0;i<s.length();i++){
string sub ="";
for(int j=i;j<s.length();j++)
{
sub+=s[j];
track[sub]++;
}
}
int maxx=0;
for(auto i:track){
if(i.first.length()>=x)
maxx = max(maxx,i.second);
}
cout<<maxx<<endl;
return 0;
}

it gave wrong answer for test case

“nskfjnzklq”
x is 1

the code gave 2 while ans should be 10

Try this :

#include<bits/stdc++.h>

using namespace std;

int main (){
string s;
map<string,int> track;
cin>>s;
int x;
cin>>x;
for(int i=0;i<s.length();i++){
string sub ="";
for(int j=i;j<s.length();j++)
{
sub+=s[j];
track[sub]++;
}
}
int maxx=0;
for(auto i:track){
if(i.first.length()>=maxx&&i.second>=x)
maxx = i.first.length()
}
cout<<maxx<<endl;
return 0;
}

yes now it gave 10…

thanks … just confirming …

will this pass for all constraints

I think it should pass .

Okay. lets hope the same …