Repeated Substring Pattern | Full Intuition | Time Complexity | GOOGLE | AMAZON | Leetcode-459

This is the 17th Video on our Strings Playlist.
In this video we will try to solve a very good and famous string problem "Repeated Substring Pattern" (Leetcode-459)

I have also explained the Maths part and also Time Complexity in this video.

We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Repeated Substring Pattern
Company Tags : GOOGLE, AMAZON

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[DurgaShiva]

kya coder ho, usse bhi badke, kya teacher ho, hats off !

[Ankitkumar-fzkc]

Thanks for this wonderful explanation . I got my approach just after the 1 minutes of video. Thanks for such a wonderful content.

[souravjoshi]

Thanks a lot man. You 2-3 minutes of intuition, and then I was able to solve it on my own. Thank you 😄

[Mukul-ko]

its'a a medium level question(leetcode ne ganja fuk ke isse easy category me dal diya), thanks for making this question really easy

[wearevacationuncoverers]

You are just amazing at explanation bro. Thanks a lot

[hemant]

Nice explanation, bhai tum to heavy driver nikle

[YashSinghal]

I just needed 20 second of intuition to do the question. Thanks!

[romanraihan]

Thinking about commenting on the slight optimization and then you have shown that too. Great explanation... Thanks a lot.

[Barry-wm]

crazzzy explaination
intuition developing explaination was🔥

[jayminrajgor]

Thanks for breaking it down so well, Mik.

[kattarohith]

can you explain approach-2 string concatenation that was mentioned in leetcode editorial

[toxic_roy]

bhaiya digit dp pe video banado plz. leetcode contest ka 4th question almost humesha ispe based hota hai. thank you

[avishkargaikwad]

Can you please make video on KMP pattern matching algorithm that can reduce the pattern matching time complexity from O(n2) to O(n)??

[dhairyachauhan]

The solution was quite streight forward but my mind told me to never construct the substring hence i got stuck :P

[dayashankarlakhotia]

Public class solution {
Public boolean repeated substring pattern (string s){
int n=s.length ();
for(int i=1;i<n;i++){
if(n%i==0){
string substring =s.substring (0, i);
stringBuilder repeated =new string builder ();
for(int j=0;j<n/i;
J++){
repeated. append (substring);
}
If(repeated. to string ().equal (s))return true;
}
}
return false;
}
};
Tc=(n*n);
sc=(n);
2nd approach.
Public class solution {
Public boolean repeated substring pattern (string s){
string doubled =s+s;
string sub=doubled. substring (1, doubled. length ()-1);
return sub.contain (s);
}
};
Tc=0(n);
sc=0(n);
For example string s=abab
doubled s=abababab;
delete 1st and last characters.
bababa.
contains Ababa return true.
2nd example s=aba;
doubled s=abaaba;
delete 1st and last.
doubled s=baab not contains. aba. return false. Thanks 🎉❤

[shivamsisodia]

Leetcode contest pe bhi video bna diya karo please 🙏🙏🙏🙏

[dikshantyadav]

shouldn't that be n^2 * sqrt(n), since in the outer loop l = 1 to n/2 and 'if condition' is checked every time for that, I understand that part inside is executed sqrt(n), and O(n) for substring operation. Since

The outer loop runs from l = 1 to l = n/2, so it runs approximately n/2 times.

Inside the outer loop, the condition n % l == 0 is checked, which takes constant time.

If the condition is satisfied, you have an inner loop that runs times = n / l times.

Inside this inner loop, you perform string concatenation using the += operator. As you've correctly pointed out, each concatenation operation takes O(m) time, where m is the length of the resulting string. In this case, the length of the resulting string is n, since you are appending n / l copies of a substring of length l. So, the inner loop takes O(n) time for each iteration.

Taking all of this into account:

The outer loop runs n/2 times.
The inner loop takes O(n) time for each iteration of the outer loop.
Hence, the total time complexity is: O(n * sqrt(n) * n) = O(n^2 * sqrt(n))

[UtkarshPatel-vo]

Bhaiya pls iska kmp algorithm wala solution bhi batayiye

[k.vabhavmishra]

Sir If you categorize the strings problems that will be good beacuse it has vast no. of problems like normal string, substring, subsequence, counting, hashing on string like this..

[amitranjan]

There is one Another cool Approach to this problem which have just 3 lines of code and works in O(N).
Idea lies in the fact that that if a string s can be constructed by repeating a substring, then concatenating two copies of s together and removing the first and last character would still contain s as a substring.
Here's the AC C++ Code
that if a string s can be constructed by repeating a substring, then concatenating two copies of s together and removing the first and last character would still contain s as a substring

bool s)
{
string S=s+s;
S=S.substr(1, S.size()-2);
return S.find(s) != string::npos;
}