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.

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

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

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 …