Help in this question

1

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
2

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
3

i have never used map.

will you please explain with code

thanks for helping

4

Ok ill post the code in 5 minutes

1 Like
5

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

6

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

i wasnt able to do it

7

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
8

Is this fine ? @noneoftheabove

9

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

10

i will understand the code

11

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

12

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
13

Ok i am posting the code

1 Like
14

which is the final code…

15

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

16

it gave wrong answer for test case

“nskfjnzklq”
x is 1

the code gave 2 while ans should be 10

17

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

18

yes now it gave 10…

thanks … just confirming …

will this pass for all constraints

20

I think it should pass .

21

Okay. lets hope the same …