The Description of the problem

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

The solutions via string perspective

class Solution {
public:
	bool repeatedSubstringPattern(string s) {
		int n = s.size();
		string ss = s + s;
		ss = ss.substr(1, 2 * n - 2);
		return ss.find(s) != string::npos;
	}
};

class Solution:
	def repeatedSubstringPattern(self, s: str) -> bool:
		n = len(s)
		ss = (s + s)[1: 2 * n - 1]
		return s in ss

The Explanations

This solution checks if the given string s can be constructed by repeating a substring of itself. The intuitive idea behind this solution is that if s can be constructed by repeating a substring of itself, then it must appear at least twice in ss, which is formed by concatenating two copies of s and removing the first and last characters. For example, let’s say s = "abab". Then ss = "abababab". After removing the first and last characters, we get ss = "bababa". Since "ab" appears twice in "bababa", we can conclude that "abab" can be constructed by repreating the substring "ab".

---

The function return true if s is found in ss using the find() method of the C++ string class. If it’s not found, it returns false.

The solutions via iteration

class Solution {
public:
	bool repeatedSubstringPattern(string s) {
		int n = s.size();
		for (int i = 1; i * 2 <= n; i++) {
			if (n % i == 0) {
				bool match = true;
				for (int j = i; j < n; j++) {
					if (s[j] != s[j - i]) {
						match = false;
					}
				}
				if (match) return true;
			}
		}
		return false;
	}
};

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n //2 + 1):
            if n % i == 0:
                if all(s[j] == s[j - i] for j in range(i, n)):
                    return True
        return False

The Explanations

The intuitive idea behind this solution to the “Repeated Substring Pattern” problem is to check all possible substrings of the given string s and see if they can be repeated to form the original string. If any such substring is found, it returns true, otherwise it returns false.

---

The function first calculates the length of s and store it in the variable n. Then it iterates over all possible substring lengths from 1 to n/2. For each substring length i, it checks if n is divisible by i. If it is, then it’s possible that a substring of length i can be repeated to form the original string.

---

The function then checks if all substrings of length i are equal. If they are, then it returns true, indicating that the original string can be constructed by repeating a substring of itself. If no such substring is found after checking all possible lengths, the function returns false.

---

For example, let’s say we have a string "abab". The function will first check it its length 4 is divisible by 1. Since it is not divisible by 1, we move on to checking if its length is divisible by 2. Since 4 is divisible by 2, we check if all substrings of length 2 are equal. In this case, "ab" and "ab" are equal so we return ture.

The solutions with next array in KMP

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next = {0};
        int pos = 0;
        for (int i = 1; i < n; i++) {
            while (pos != 0 && s[pos] != s[i]) {
                pos = next[pos - 1];
            }
            if (s[pos] == s[i]) pos++;
            next.push_back(pos);
        }
        return next[n-1] && (n % (n - next[n-1]) == 0);
    }
};