Longest Common Prefix
An easy Strings interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Strings
- Sheets
- 2
- Core for
- 14 roles
The problem
Given an array of strings, find the longest common prefix shared by all strings.
Example 1
- Input
- ["interview","internet","internal"]
- Output
- "inter"
Example 2
- Input
- ["alpha","beta","gamma"]
- Output
- ""
Example 3
- Input
- ["interspecies","interstellar","interstate"]
- Output
- "inters"
Constraints
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
How to think about it
Updated 2026-09-29The shared prefix cannot outlast the first mismatch across any pair of words. Scan column by column across all strings simultaneously. The first column where any word runs out of characters or contains a differing letter marks the definitive end of the common prefix.
Approaches, worst first
Horizontal pairwise reduction
time O(S) · space O(1)
Initialize the candidate prefix as strs[0]. For each subsequent string, shorten the prefix until the current string starts with it. If the prefix ever shrinks to empty, terminate early. Performs well on average but compares redundant trailing characters when the first two strings are exceptionally long.
Vertical character scanWrite this one
time O(S) · space O(1)
Iterate character index col through the first string. For each col, verify that every other string in the list has length > col and matches strs[0][col]. Halt and slice strs[0][0..col] at the very first mismatch or exhausted word.
Where people lose marks · 3
- An empty string inside strs immediately forces the common prefix to empty; index bounds check is essential before indexing character positions.
- Single-string array: a list with only one string must return that whole string.
- Assuming all strings are equal length; a shorter string running out of characters must end the prefix search cleanly without index-out-of-range errors.
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 .