Pattern visualizer

Repeated String Match

The trap here is not knowing when to stop repeating. Two facts pin it down. The repetition must be at least as long as b, which sets the floor at ceil(len(b) / len(a)) copies. And one extra copy on top of that is always enough: any occurrence of b can be shifted left by whole copies until it starts inside the very first copy, and from there it can run no further than one copy past the floor. So exactly two candidates need testing — the floor and the floor plus one. If neither works, no number ever will, and the search is over after two scans instead of an infinite loop. Animated on: a = "abcd", b = "cdabcdab" — repeat a the fewest times so that b is a substring of the result, or return -1 if that is impossible..

Two candidate repetitions, and a reason there is never a third

time O(n * m)space O(n + m)step 1 / 9

[0]

[1]

[2]

[3]

line 2

a = "abcd" is 4 characters and b = "cdabcdab" is 8. A string can never contain something longer than itself, so 2 copies (8 characters) is the smallest repetition worth testing at all.

Pseudocode

1FUNCTION repeatedStringMatch(a, b):
2  k <- CEIL(LENGTH(b) / LENGTH(a))
3  FOR copies <- k TO k + 1:
4    s <- REPEAT(a, copies)
5    FOR i <- 0 TO LENGTH(s) - LENGTH(b):
6      m <- 0
7      WHILE m < LENGTH(b) AND s[i + m] = b[m]:
8        m <- m + 1
9      IF m = LENGTH(b):
10        RETURN copies
11  RETURN -1

← / → step · space play · Home restart

Where to practice Strings

Practice Strings problems All Strings problems Back to roadmap