LeetCode 459. Repeated Substring Pattern (Algorithm Explained)

Показать описание

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

Рекомендации по теме

Комментарии

For those who are wondering why he chose
option-1) "for(int i = len/2; i>=1; i--)"
and not
option-2) "for(int i = 1; i<=len/2; i++)"

Let's take a small example to find which is better :
s = "abcabcabcabc"

If we chose option-1, we can find "abcabc" is the substring which when repeated "twice" gives the string s.

If we chose option-2, we can find "abc" is the substring which when repeated "4 times" gives the string s.

So, obviously option-1 is better as we are looking for the largest repeated substring first to minimize repetitions count (inner loop) and then moving towards smallest.

Hope that helps.

codestorywithMIK

It is easy if you solved it in O(n^2) time but to solve it in O(n), it is hard if you don't know KMP algorithm, medium if you know it.

CodingForRealLife

Saw this method in leetcode discussion, smart people are everywhere :)
class Solution {
public boolean s) {
int idx = (s + s).indexOf(s, 1);
return idx < s.length();
}
} basically, if s contains multiple copies of substring, when try to find s in ss (ss = s + s), the first occurrence of s should be within the length of first s. Otherwise, it would be the beginning of second s.

jonfit

Straightforward solution but the runtime is slow (100+ms). If performance is of concern, I suggest taking a look at this rotation technique that compares the two overlapping substrings and compare if they are equal. This results in just 20~30ms runtime.
::::C++ implementation::::
class Solution {
public:
bool s) {
int len = (int)s.length();
string sub_s;
int k;
for (int i = 1; i <= (len / 2); ++i) {
if (len % i == 0 && s.substr(0, len - i) == s.substr(i)) { // rotation technique
return true;
}
}
return false;
}
};

ianpan

public boolean s) {
String a1=s+s;
String a2=a1.substring(1, a1.length()-1);
if(a2.contains(s)) return true;
else return false;
}

sukeshreddy

I really enjoy ur channel man. Really good advice here. Can you do a video on some practical projects that can look good for employers? I feel like that area is my weakness right now. I would really appreciate your advice there.

iloveallparties

Bro can you please make a video on KMP solution for this question.

niteshnijhawan

Hey Nick, is there a specific type of leetcode problem that is common in technical interviews? I’m currently going through each problem and I have no idea which types to focus on.

joecamroberon

Can be more optimize if u will take all the divisors of the length by sqrt(len).

codeminatiinterviewcode

that should be covered with the KMP (prefix that is also a suffix)... again, if you want to ace a code interview, come up with a brute force approach is probably not going to fly in a real interview.

b

A nick has ive been learning java in school but I NEED to REALLY work on problem-solving, I want to know is Leet Code a good beginner place to start

ILovETRicKShoTnMW

Hey man can you help with 132 pattern?

sourishisavailable

hey nick plz make a video on implementation of strstr leetcode ...

ananyadwivedi

Can you do more medium difficulty graph problems please? Thanks

matthewlev

Getting compile time error : for(int i =len/2; i >= 1;i--)
{
if(len%i==0)
{
int num_repeats = len/i;

String substring = s.substring(0, i);

StringBuilder sb = new StringBuilder();
sb.append(substring);

}
return true;
// Compilation Error

}

}
This is outside the if loop and giving an error . I was just trying your code in Eclipse. Do let me know If I am doing something wrong here.

ved

The best way to solve this problem is KMP algorithm.

stacywen

your solution awesome I like all great help
static boolean input){
for (int i = 0; i < input.length(); i++) {
if && input.substring(i+2).contains(input.substring(i, i+2))){
return true;
}
}
return false;
}

wasuvansundararajan

dont explain the solution, explain the intution behind it please

Ubaiish

Can you do a series on top liked questions of leetcode

vraih

This solution is incorrect. It is not an "easy" problem if one is not familiar with the KMP algo.

But nice video, thank you for your effort.

spongebobsquarepants

LeetCode 459. Repeated Substring Pattern (Algorithm Explained)

LeetCode 459. Repeated Substring Pattern (Algorithm Explained)

LeetCode 459 - Repeated Substring Pattern Solved (Java)

Repeated Substring Pattern | LeetCode 459 | C++, Java, Python

leetcode 459. Repeated Substring Pattern

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

Repeated Substring Pattern | Leet code 459 | Theory explained + Python code

459. Repeated Substring Pattern - LeetCode Daily Challenge - JavaScript

459. Repeated Substring Pattern - Day 21/31 Leetcode August Challenge

Repeated Substring Pattern | Leetcode September Challenge (Day3) | Leetcode 459

Repeated substring pattern problem (LeetCode #459) [3 solutions] - Inside code

LeetCode 459 - Repeated Substring Pattern (full version on tiktok)

Repeated Substring Pattern - LeetCode #459 with Python, JavaScript and Java

Leetcode - Repeated Substring Pattern (Python)

Repeated Substring Pattern | LeetCode 459 | Java, Python

[SOLVED!] Repeated Substring Pattern - LeetCode 459 - Java

repeated substring pattern leetcode | leetcode 459 | two pointer | regex

Leetcode 459 Repeated Substring Pattern - A Google Amazon Interview Question

Repeated Substring Pattern - LeetCode 459 - Python

459. Repeated Substring Pattern - Day 3/30 Leetcode September Challenge

Leetcode 459: Repeated Substring Pattern | Easy Explanation & Solution

LeetCode 459. Repeated Substring Pattern 2 Mind-Blowing Approaches to a Classic Coding Problem

Leetcode #459 - Repeated Substring Pattern - Python

LEETCODE 459: Repeated Substring Pattern #leetcode #codingchallenge #dsa #stringleetcode

LeetCode 459.Repeated Substring pattern