459. Repeated Substring Pattern

Problem Statement

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Example 1:

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Example 2:

Input: s = "aba"
Output: false

Example 3:

Input: s = "abcabcabcabc"
Output: true
Explanation: It is the substring "abc" four times or the substring "abcabc" twice.

Constraints:

1 <= s.length <= 104
s consists of lowercase English letters.

Intuition

Approach 1:
Take substrings and repeat to check if exists

Approach 2:

s = abab
Repeat and delete first and last character
abab + abab

a)bababa(b
Now try to find abab in this

Links

https://leetcode.com/problems/repeated-string-match/description/

Video Links

Approach 1:

Brute

C++

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();

        for(int i=1; i<=n/2; i++){
            if(n%i == 0){
                string temp = s.substr(0,i);
                string repeat = "";

                for(int j=0; j<n/i; j++){
                    repeat += temp;
                }

                if(repeat == s)
                    return true;
            }
        }

        return false;
    }
};

Approach 2:

Optimal trick

C++

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string rept = s + s;
        string monk = rept.substr(1, rept.size()-2);

        if(monk.find(s) != -1)
            return true;

        return false;
    }
};

Approach 3:

C++

Approach 4:

C++