DSA problem
Repeated String Match
Given two strings a and b, return the minimum number of times you must repeat a so that b becomes a substring of the repeated string. If no such number of repetitions makes b a substring of repeated a, return -1.
The key observation is a tight upper bound on how many repetitions are ever needed. If b is a substring of a repeated some number of times, then b aligns somewhere inside the repetition. Building enough copies so that the total length is at least |a| + |b| is always sufficient: any further repetition would only add another full copy of a, which cannot create a new substring placement of b that did not already exist.
This leads to a clean strategy. Repeat a until its length is at least |b| — call this count k. Check whether b is a substring of the resulting string; if yes, return k. Otherwise, append one more copy of a and check again; if it now matches, return k + 1. If neither attempt succeeds, no number of repetitions can ever work, so return -1.
This bound holds because any successful match must start within the first copy of a (every later start is just a shifted version of an earlier one), and from any start position within the first copy, the match cannot extend beyond |a| + |b| characters. Total work is therefore O((|a| + |b|) * |b|) using built-in substring search, or O(|a| + |b|) if KMP is used internally.
Examples
a = "abcd", b = "cdabcdab"3a = "a", b = "aa"2a = "abc", b = "wxyz"-1Constraints
- 1 <= a.length, b.length <= 10^4
- a and b consist of lowercase English letters.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.