↓ Skip to main content
Dawn Magnet’s Site
LeetCode 686: Repeated String Match

LeetCode 686: Repeated String Match

·225 words·2 mins· loading · loading ·
Author
Dawn Magnet
Tech enthusiast & daily solver.

Given two strings a and b, find the minimum number of repetitions of string a such that b is a substring of the repeated string. Return -1 if this is impossible.

Note: Repeating the string "abc" 0 times produces "", repeating it 1 time produces "abc", and repeating it 2 times produces "abcabc".

 

Example 1:

Input:a = "abcd", b = "cdabcdab"
Output:3
Explanation:After repeating a three times, the result is "abcdabcdabcd", so b is a substring.

Example 2:

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

Example 3:

Input:a = "a", b = "a"
Output:1

Example 4:

Input:a = "abc", b = "wxyz"
Output:-1

 

Constraints:

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

Analysis
#

First obtain the lengths of the two strings, a and b. Let n be the ceiling of b/a. According to the problem, b can only be a substring of a repeated n times, a repeated n+1 times, or neither. If neither contains b, return -1.

Rust Code
#

impl Solution {
    pub fn repeated_string_match(a: String, b: String) -> i32 {
        let (lb, la) = (b.len(), a.len());
        let times = ((lb as f64) / (la as f64)).ceil() as usize;
        if a.repeat(times).contains(&b) {
            times as i32
        } else if a.repeat(times + 1).contains(&b) {
            times as i32 + 1
        } else {
            -1
            }
    }
}