459. Repeated Substring Pattern

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

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.

Concept

The repeated substring problem has a rather twisted solution. We can say that to find whether a substring can be repeated to construct the original string, we could:

1. Find the repeating substring and check if the string consists only of its consecutive entries.
2. Repeat the original string twice and look for substring from the 1st index instead of 0th.

We go with the 2nd method as its the most efficient. Instead of repeating the substring, we repeat the original string. On occurance of substring in string, it must be at a position less than the length of the original string. This ensure that the substring found isn’t the beginning of our concatenated string.

Solution

Algorithm

1. Repeat the original string twice by concatenating with itself.
2. Start from index 1 and search for substring.
3. if Found, check its position
   1. If position < length of original string, return true
   2. Else return false

Complexity

Time	Space
O(n)	O(n)

Implementation

bool repeatedSubstringPattern(char* s) {
 
    char *double_string = (char *)calloc(strlen(s)*2 + 1, 1);
 
    strcpy(double_string, s);
 
    strcat(double_string, s);
 
    char *ptr = strstr(double_string+1, s);
 
    if (ptr == NULL) return false;
 
    else if (ptr - double_string < strlen(s)) return true;
 
    else return false;
 
}