Welcome to Subscribe On Youtube

686. Repeated String Match

Description

Given two strings a and b, return the minimum number of times you should repeat string a so that string b is a substring of it. If it is impossible for b​​​​​​ to be a substring of a after repeating it, return -1.

Notice: string "abc" repeated 0 times is "", repeated 1 time is "abc" and repeated 2 times is "abcabc".

 

Example 1:

Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

Example 2:

Input: a = "a", b = "aa"
Output: 2

 

Constraints:

• 1 <= a.length, b.length <= 104
• a and b consist of lowercase English letters.

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int repeatedStringMatch(String a, String b) {
          int m = a.length(), n = b.length();
          int ans = (n + m - 1) / m;
          StringBuilder t = new StringBuilder(a.repeat(ans));
          for (int i = 0; i < 3; ++i) {
              if (t.toString().contains(b)) {
                  return ans;
              }
              ++ans;
              t.append(a);
          }
          return -1;
      }
  }
  

• class Solution {
  public:
      int repeatedStringMatch(string a, string b) {
          int m = a.size(), n = b.size();
          int ans = (n + m - 1) / m;
          string t = "";
          for (int i = 0; i < ans; ++i) t += a;
          for (int i = 0; i < 3; ++i) {
              if (t.find(b) != -1) return ans;
              ++ans;
              t += a;
          }
          return -1;
      }
  };
  

• class Solution:
      def repeatedStringMatch(self, a: str, b: str) -> int:
          m, n = len(a), len(b)
          ans = ceil(n / m)
          t = [a] * ans
          for _ in range(3):
              if b in ''.join(t):
                  return ans
              ans += 1
              t.append(a)
          return -1
  
  

• func repeatedStringMatch(a string, b string) int {
  	m, n := len(a), len(b)
  	ans := (n + m - 1) / m
  	t := strings.Repeat(a, ans)
  	for i := 0; i < 3; i++ {
  		if strings.Contains(t, b) {
  			return ans
  		}
  		ans++
  		t += a
  	}
  	return -1
  }
  

• function repeatedStringMatch(a: string, b: string): number {
      const m: number = a.length,
          n: number = b.length;
      let ans: number = Math.ceil(n / m);
      let t: string = a.repeat(ans);
  
      for (let i = 0; i < 3; i++) {
          if (t.includes(b)) {
              return ans;
          }
          ans++;
          t += a;
      }
  
      return -1;
  }
  
  

All Problems

All Solutions