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 <= 10**4
• s consists of lowercase English letters.

Solve¶

Brute force¶

python

The easiest way to do any problem, is that we check all possible solution, we already have a conclusion that from the problem given

we can create s by appending multiple copies of sub substring of s

Which mean, len(s) % len(sub) == 0

After that, we just check one by one if our sub string is on repeat or not by split s into multiple substring with length equal to the length of sub string.

While this generally a bad way to solve this question, but in python:

• String comparing always a hash compare, which cost less than a full string comparing one by one character
• We doing way less than 10**4 on the first loop, as we have to enforce len(s) % len(sub) == 0 before doing the second loop

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n):
            if n % i != 0:
                continue

            sub = s[:i]
            res = True
            for step in range(n//i):
                if sub != s[step*i: (step+1) * i]:
                    res = False
                    break
            if res:
                return True

        return False

Rust brute force¶

rust

While thinking about it, I too, checking how rust implement the string comparing. As there isn’t much different when I try to implement the same code line by line in rust

struct Solution;

impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        let n = s.len();
        for i in 1..n {
            if n % i != 0 {
                continue;
            }

            let sub = &s[..i];
            let mut res = true;
            for step in 0..(n / i) {
                if sub != &s[step * i..(step + 1) * i] {
                    res = false;
                    break;
                }
            }
            if res {
                return true;
            }
        }

        false
    }
}

fn main() {
    let s = String::from("abbabb");
    let result = Solution::repeated_substring_pattern(s);
    println!("Result: {}", result);
}