Repeated Substring Pattern

                                            
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                string sub = s.substr(0, i);
                string temp = "";
                for (int j = 0; j < n / i; j++) {
                    temp += sub;
                }
                if (temp == s) {
                    return true;
                }
            }
        }
        return false;
    }
};

                                            
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                String sub = s.substring(0, i);
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n / i; j++) {
                    sb.append(sub);
                }
                if (sb.toString().equals(s)) {
                    return true;
                }
            }
        }
        return false;
    }
}

                                            
class Solution(object):
    def repeatedSubstringPattern(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return s in (s + s)[1:-1]

                                            
bool repeatedSubstringPattern(char* s) {
    int len = strlen(s);
    for (int i = 1; i <= len / 2; i++) {
        if (len % i == 0) {
            int flag = 1;
            for (int j = i; j < len; j++) {
                if (s[j] != s[j % i]) {
                    flag = 0;
                    break;
                }
            }
            if (flag)
                return true;
        }
    }
    return false;
}

                                            
public class Solution {
    public bool RepeatedSubstringPattern(string s) {
        string str = s + s;
        return str.Substring(1, str.Length - 2).Contains(s);
    }
}

                                            
/**
 * @param {string} s
 * @return {boolean}
 */
const repeatedSubstringPattern = (s) => {
    for (let i = 1; i <= s.length / 2; i++) {
        if (s.length % i === 0) {
            const substr = s.slice(0, i);
            if (substr.repeat(s.length / i) === s) {
                return true;
            }
        }
    }
    return false;
};

                                            
function repeatedSubstringPattern(s: string): boolean {
    const n = s.length;
    for (let i = 1; i <= n / 2; i++) {
        if (n % i === 0) {
            const subStr = s.substring(0, i);
            let repeated = true;
            for (let j = i; j < n; j += i) {
                if (s.substring(j, j + i) !== subStr) {
                    repeated = false;
                    break;
                }
            }
            if (repeated) {
                return true;
            }
        }
    }
    return false;
};

                                            
class Solution {
    /**
     * @param String $s
     * @return Boolean
     */
    function repeatedSubstringPattern($s) {
        $n = strlen($s);
        for ($i = 1; $i <= $n / 2; $i++) {
            if ($n % $i == 0 && $s == str_repeat(substr($s, 0, $i), $n / $i)) {
                return true;
            }
        }
        return false;
    }
}

                                            
import kotlin.math.sqrt

class Solution {
    fun repeatedSubstringPattern(s: String): Boolean {
        val n = s.length
        for (i in 1..n / 2) {
            if (n % i == 0) {
                val sub = s.substring(0, i)
                if (s == sub.repeat(n / i)) {
                    return true
                }
            }
        }
        return false
    }
}

                                            
class Solution {
  bool repeatedSubstringPattern(String s) {
      int n = s.length;
      for (int i = 1; i <= n ~/ 2; i++) {
          if (n % i == 0) {
              String sub = s.substring(0, i);
              String newStr = '';
              for (int j = 0; j < n ~/ i; j++) {
                  newStr += sub;
              }
              if (newStr == s) {
                  return true;
              }
          }
      }
      return false;
  }
}

                                            
func repeatedSubstringPattern(s string) bool {
    size := len(s)
    for i := 1; i <= size/2; i++ {
        if size%i == 0 {
            sub := s[:i]
            if strings.Repeat(sub, size/i) == s {
                return true
            }
        }
    }
    return false
}

                                            
# @param {String} s
# @return {Boolean}
def repeated_substring_pattern(s)
    (s + s)[1..-2].include? s
end

                                            
object Solution {
    def repeatedSubstringPattern(s: String): Boolean = {
        (s + s).substring(1, 2 * s.length - 1).contains(s)
    }
}

                                            
impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        let double_s = format!("{}{}", s, s);
        double_s[1..double_s.len() - 1].contains(&s)
    }
}

To solve this coding challenge, you need to determine whether a given string \( s \) can be generated by repeating a substring of itself multiple times. Let's break this down step-by-step and provide a detailed explanation followed by pseudocode.

Explanation

Problem Understanding :

We are given a string \( s \).
We need to check if this string can be constructed by taking a substring of it and concatenating multiple copies of this substring.

Example Analysis :

For the input "abab": If we take the substring "ab" and repeat it twice, we get the original string. Hence, the output will be
true

.
For the input "aba": No substring, when repeated, can recreate "aba". Hence, the output will be
false

.
For the input "abcabcabcabc": Both "abc" (repeated four times) and "abcabc" (repeated twice) can recreate the original string. Hence, the output will be
true

.

Efficient approach :

A direct way to check for the repeated substring pattern involves manipulating the string in such a manner that we can directly find repetitions.
If we concatenate the string with itself (let's call this new string
s_new

), we can identify a repeated pattern if the original string (excluding its first and last characters) exists within this new concatenated string.
This method works because if \( s \) can be created by repeating a substring, then doubling \( s \) and removing the first and last characters should still contain \( s \) within it.

Detailed Steps in Pseudocode

Concatenate the string with itself :

Let's create a new string that is the original string
s

concatenated with itself, resulting in
s_new

.

Remove the first and last character from
s_new

:

By removing the first and last character from
s_new

, we search for the original string
s

in this modified
s_new

.

Check if the original string exists in this modified string :

If the original string
s

is found in this modified doubled string, it indicates that the original string can be built by repeating a substring.

Here is the pseudocode reflecting this logic with detailed comments:

                                            
// Function to determine if string s can be constructed by repeating a substring
function repeatedSubstringPattern(original_string):
    // Step 1: Concatenate the string with itself 
    doubled_string = original_string + original_string
    
    // Step 2: Remove the first and last character from the doubled string
    modified_doubled_string = doubled_string[1:-1]
    
    // Step 3: Check if the original string exists in the modified doubled string
    if original_string is in modified_doubled_string:
        return true  // The original string can be constructed by repeating a substring
    else:
        return false  // The original string cannot be constructed by repeating a substring

// Let's test the function with the given examples
print(repeatedSubstringPattern("abab"))  // Expected output: true
print(repeatedSubstringPattern("aba"))   // Expected output: false
print(repeatedSubstringPattern("abcabcabcabc"))  // Expected output: true

In summary, this approach provides an effective and efficient way to determine if a string is made up by repeating a substring pattern, leveraging string manipulation and simple checks for substring existence. Each step is designed to keep the complexity manageable even for longer strings.