String Tricks

What is this?

None of these needs an algorithm in the usual sense. Each is cracked by working out what the answer must look like — that a periodic string reappears inside a doubled copy of itself, that the longest uncommon subsequence can only be one of the two inputs, that the number of repetitions needed is bounded by a length calculation.

The habit being trained is to reason about structure first and reach for a loop second.

💡 Fun fact: Repeated Substring Pattern has a one-line solution that looks like a magic trick: s is built from a repeated block if and only if s appears inside (s + s) with the first and last characters removed. Doubling the string creates every rotation of it as a substring, and a periodic string is one that matches a non-trivial rotation of itself. Stripping the ends is what excludes the trivial match at position 0.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: reason about what the answer must be before searching for it — a period shows up as a self-rotation, an uncommon subsequence can only be a whole input, and the number of repetitions has a computable ceiling.

1. Periodicity as a self-rotation

def repeated_substring_pattern(s):
    return s in (s + s)[1:-1]

Doubling the string places every rotation of s somewhere inside it. If s is abcabc, then abcabcabcabc contains abcabc starting at position 3 as well as 0 and 6. Stripping one character from each end removes the two trivial occurrences, so a remaining match proves a non-trivial rotation equals s — which is exactly periodicity.

The alternative is to test each candidate block length that divides n, which is O(n · d(n)) and perfectly acceptable to offer first.

2. The problem that is not a problem

Longest Uncommon Subsequence I asks for the longest subsequence of one string that is not a subsequence of the other. The reasoning:

• If the strings are equal, every subsequence of one is a subsequence of the other → answer -1.
• If they differ, the longer string is not a subsequence of the shorter one (it is too long), and if they are the same length but different, neither is a subsequence of the other.

So the answer is -1 when equal, otherwise max(len(a), len(b)). Recognising that no search is required is the solution, and being able to state the argument matters more than the two lines of code.

3. Bound the repetitions

For Repeated String Match, a must be repeated enough times to be at least as long as b, plus possibly one more copy to cover an offset start:

minimum = ceil(len(b) / len(a))
try minimum, then minimum + 1 — if neither contains b, it is impossible

Two candidates suffice. Any further copy adds nothing: if b fits at all, it fits within a window of len(b) + len(a) characters, which those two candidates already cover.

4. Bijection needs two maps

Isomorphic Strings requires a one-to-one mapping in both directions. One map alone accepts "badc" → "baba", because d and c can both map to a when nothing checks the reverse:

forward, backward = {}, {}
for x, y in zip(s, t):
    if forward.setdefault(x, y) != y or backward.setdefault(y, x) != x:
        return False
return True

5. A 30-second worked example (self-rotation)

s = "abab"
s + s          = "abababab"
(s + s)[1:-1]  = "ababab"        strip the first and last characters
is "abab" in "ababab"?  yes, at index 0 and index 2 → True ✓

s = "aba"
s + s          = "abaaba"
(s + s)[1:-1]  = "baab"
is "aba" in "baab"?  no → False ✓

"abab" is "ab" twice, so it is periodic. "aba" has no repeating block, and the stripped double correctly refuses to contain it.

6. Where you'll actually meet this

• Compression. Detecting a repeating period is the first step in run-length and dictionary encoding.
• Signal and log analysis. Identifying cyclic patterns in event sequences.
• Data validation. Bijection checks — isomorphism between two encodings — appear in schema and mapping validation.
• Search. Rotation-aware matching, used in circular buffers and rotated-text search.
• Cryptanalysis. Period detection in a keystream is exactly the repeated-substring question.

7. Problems in this chapter

▶ Repeated Substring Pattern

Is the string built from a repeated block? Check whether s occurs in (s + s)[1:-1], or test each divisor block length.
Pattern: self-rotation test. Target: O(n) with the doubling trick.

▶ Longest Uncommon Subsequence I

Longest subsequence of one string that is not one of the other. -1 if equal, else the longer length.
Pattern: reason to the answer. Target: O(n) time.

▶ Repeated String Match

Fewest repetitions of a so that b becomes a substring. Try ceil(len(b)/len(a)) and one more.
Pattern: bounded candidate count. Target: O(len(a) + len(b)) with an efficient search.

▶ Isomorphic Strings

Is there a one-to-one character mapping between the strings? Two maps, checked in both directions.
Pattern: bijection with twin maps. Target: O(n) time, O(1) space for a fixed alphabet.

8. Common pitfalls 🚫

• Forgetting to strip the ends in the doubling trick. s always appears in s + s at position 0, so without [1:-1] every string reports as periodic.
• Using one map for isomorphism. It accepts two characters mapping to the same target; the reverse map is mandatory.
• Trying every repetition count. Two candidates suffice, and the argument for why is the answer.
• Comparing lengths but not content in the uncommon-subsequence problem. Equal-length different strings still return that length.
• Assuming the strings are the same length in isomorphism — check first, or zip silently truncates.
• Overusing the clever one-liner. Offer the divisor-testing version too; interviewers often want to see you can derive it, not just recall it.

9. Key takeaways

1. Reason about the answer's structure first. Three of these four need no search at all.
2. Doubling a string exposes its rotations, which is what makes periodicity a substring test.
3. Strip the trivial match or the test always passes.
4. Bijections need both directions checked.
5. Bound the candidates. Two repetition counts cover every case that can work.
6. Some problems have no algorithm — recognising that quickly is the skill being tested.
7. Why interviewers like it: these separate candidates who explore a problem's structure from those who immediately start writing loops.

Order: Repeated Substring Pattern → Longest Uncommon Subsequence I → Repeated String Match → Isomorphic Strings.