Z-Algorithm
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
Compute the Z-array of a string, where Z[i] is the length of the longest substring starting from position i that matches a prefix of the string.
Example 1
- Input
- "aaaaa"
- Output
- [5,4,3,2,1]
Example 2
- Input
- "abacaba"
- Output
- [7,0,1,0,3,0,1]
Example 3
- Input
- "aabxaabxcaabxaabxay"
- Output
- [19,1,0,0,5,1,0,0,1,7,1,0,0,5,1,0,0,1,0]
Constraints
- 1 <= s.length <= 10^5
- s consists of lowercase English letters
How to think about it
Updated 2026-09-29Maintain an interval [L, R] representing the furthest-reaching segment matching a prefix seen so far. For any index i inside [L, R], its corresponding position in the prefix is i - L. You can copy the previously computed Z value Z[i - L] directly, and only spend new character comparisons extending beyond R when the match hits or exceeds the right boundary.
Approaches, worst first
Naive prefix comparison
time O(n^2) · space O(1)
For each index i from 0 to n - 1, compare characters s[i + k] with s[k] from k = 0 until mismatch. Repeats comparisons over identical prefixes, suffering quadratic time on repeated strings like 'aaaaa'.
Linear Z-box maintenanceWrite this one
time O(n) · space O(1)
Keep the rightmost matching window [L, R]. If i <= R, initialize Z[i] with min(R - i + 1, Z[i - L]). Then expand naively past R as far as characters match, and update [L, R] whenever the match extends past the previous R. Each character is compared successfully at most once.
Where people lose marks · 3
- Value at Z[0]: the convention in competitive programming and problem specifications often sets Z[0] = n (as in the problem examples) or 0. Follow the example convention where Z[0] is string length.
- Blindly setting Z[i] = Z[i - L] when i + Z[i - L] exceeds R: you can only guarantee equality up to R; characters beyond R must be checked explicitly.
- Off-by-one bounds when updating R: if an expansion reaches index k, the new window bounds become L = i and R = k - 1.
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 .