Repeated String Match
A medium Strings interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Strings
- Sheets
- 1
- Core for
- 14 roles
The problem
Find the minimum number of times string A must be repeated so that string B is a substring of the repeated string.
Example 1
- Input
- A="abcd", B="cdabcdab"
- Output
- 3
Example 2
- Input
- A="a", B="aa"
- Output
- 2
Example 3
- Input
- A="abc", B="wxyz"
- Output
- -1
Constraints
- 1 <= A.length, B.length <= 10^4
How to think about it
Updated 2026-09-29For B to fit inside a repeated string of A, the total length of the repetition must be at least as long as B. If repeating A up to that minimum length still leaves B straddling an outer boundary, appending A exactly one more time covers all possible offset alignments. If B is still not found after that extra copy, repeating further will never help.
Approaches, worst first
Character-by-character modular offset scanning
time O(n * m) · space O(1)
Test each possible start index i in A where B could match, comparing B[j] with A[(i + j) % A.length]. If a mismatch occurs, restart matching from the next starting index in A. Repeatedly verifying overlapping character sequences from scratch without prebuilt pattern search routines runs into worst-case quadratic comparisons.
Bounded string expansion with substring searchWrite this one
time O(n + m) · space O(n + m)
Repeat A until its accumulated length is >= B.length. Check if B is a substring; if so, return the repetition count. If not, append A once more and check again. If still absent, B cannot possibly appear as a substring of any repetition of A, so return -1.
Where people lose marks · 3
- Stopping right at ceil(B.length / A.length) without checking one additional copy: B may begin near the end of the first copy of A and terminate inside an extra copy at the tail.
- Characters in B that do not exist anywhere in A: checking character sets beforehand can save needless string concatenation.
- Excessive repetition in an unbounded while-loop: repeating beyond count + 1 wastes memory and risks time limit exceeded when B is impossible.
The theory behind it
Strings — the ground this problem stands on. All Strings problems
What Strings is
A string is an ordered necklace of text characters, like letters printed along a ribbon of paper. Each character sits at an exact numeric slot, holding a glyph such as a letter, punctuation mark, or digit. In many programming languages, ribbons cannot be edited after creation, meaning changing a single character requires pressing an entirely new ribbon from scratch.
When to reach for it
Reach for string techniques when inputs consist of words, DNA sequences, serialized data formats, or sentences. Clues include questions testing palindromes, anagram matches, substring patterns, parenthesis balancing, or character frequency counts. Whenever an algorithm asks to transform capitalization, parse structured tokens, or compute edits between two phrases, string representations are the core subject.
How the pattern works
Think of characters as small integer codes ranging across standard character sets. Frequency tables with fixed sizes often replace heavy hash maps when tallying occurrences. For search tasks, maintain rolling state using character indices or sliding borders. When building output text through repeated appends, accumulate pieces inside a mutable list or string builder rather than concatenating strings directly, avoiding quadratic copy overhead.
More Strings problems
Target Roles
Core requirement for 14 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .