2023-08-21 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 21

Description

Repeated Substring Pattern

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.

Solution

class Solution {
public:
  bool repeatedSubstringPattern(string s) {
    int len = s.length();
    if(len == 1) return false;
    vector<int> factors;
    for(int i = 1; i * i <= len; ++i) {
      if(len % i == 0) {
        factors.push_back(i);
        if(i * i != len && i != 1) factors.push_back(len / i);
      }
    }
    for(auto factor : factors) {
      bool ok = true;
      for(int pos = factor; pos < len && ok; ++pos) {
        if(s[pos % factor] != s[pos]) {
          ok = false;
        }
      }
      if(ok) return true;
    }
    return false;
  }
};

// Accepted
// 129/129 cases passed (18 ms)
// Your runtime beats 67.67 % of cpp submissions
// Your memory usage beats 93.58 % of cpp submissions (9.4 MB)
Algorithm