Abstract / Summary

Find the longest starting part that is the same in all words in a list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 48% (10+ million submissions).

Typical patterns to solve this problem:

• Array
• String
• Trie

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The presented implementation solves the classic longest common prefix problem for a collection of strings. It iteratively examines characters at the same position across all input strings, advancing a counter while the characters remain identical. Once a mismatch or an insufficient length is detected, the loop terminates and the prefix up to the recorded length is extracted from the first string. The algorithm is compact, relies on a single pass over the characters, and avoids auxiliary containers.

Initialization

At the start of the function a counter named result is set to zero. This counter represents the length of the common prefix discovered so far.

int result = 0;

The counter is the only mutable state used throughout the computation, which keeps the memory footprint minimal.

Main Loop

The core of the algorithm is an infinite while (true) loop that continues until a condition forces a break. Inside the loop a boolean flag ok is assumed true at the beginning of each iteration. The flag is used to detect any violation of the prefix condition.

while (true)
{
    bool ok = true;
    for (auto& s : strs)
        if (s.size() < result ||
            s[result] != strs[0][result])
        {
            ok = false;
            break;
        }

    if (!ok)
        break;

    result++;
}

The inner for loop iterates over every string in the input vector. For each string it checks two situations:

• Whether the current string is shorter than the current prefix length (s.size() < result). If this is true, the prefix cannot be extended because at least one string ends before the next character.
• Whether the character at the current index result differs from the character at the same position in the first string (s[result] != strs[0][result]). A mismatch indicates that the common prefix ends before this index.

If either condition holds, the flag ok is set to false and the loop exits early. The early exit prevents unnecessary comparisons once a mismatch is found, which is a key performance optimization. When all strings satisfy the conditions, the flag remains true and the counter result is incremented, extending the candidate prefix by one character.

Result Construction

After the loop terminates, the function returns a substring of the first string, starting at position zero and spanning the length stored in result. This substring is precisely the longest common prefix shared by all input strings.

return strs[0].substr(0, result);

Using substr on the first string avoids constructing a new string character by character, leveraging the standard library’s efficient substring operation.

Edge Cases Handled

The algorithm gracefully handles several edge scenarios:

• When the input vector contains strings that share no common starting character, the inner loop detects a mismatch at the very first index, leaving result at zero. The final substring call then returns an empty string, representing the absence of a common prefix.
• If one of the strings is empty, the size check (s.size() < result) becomes true as soon as result attempts to exceed zero, causing an immediate break and yielding an empty prefix.
• When all strings are identical, the loop continues until result reaches the length of the shortest string. At that point the size check fails for any string that cannot be indexed further, and the loop stops, returning the full content of the shortest (and therefore common) string.
• For a single-element vector, the inner loop compares the sole string against itself, which always succeeds. The loop proceeds until the index reaches the length of that string, after which the size condition stops further advancement, and the entire string is returned as the common prefix.

Performance Optimizations

The implementation incorporates several subtle optimizations that contribute to its efficiency:

• The use of a single integer counter eliminates the need for additional data structures such as auxiliary arrays or hash maps, keeping the algorithm’s memory usage low.
• The early break from the inner for loop as soon as a mismatch is detected prevents the algorithm from scanning the remaining strings in the current iteration, reducing the number of character comparisons in cases where the prefix diverges early.
• By referencing the first string directly (strs[0][result]) for comparison, the code avoids repeated lookups or copying of characters, ensuring that each character access is a constant-time operation.
• The final extraction of the prefix via substr leverages the standard library’s internal optimizations for creating a view of the original string without copying the entire content, especially when the underlying implementation employs copy-on-write or reference counting.

Overall, the solution delivers a concise and effective approach to determining the longest common prefix, balancing simplicity with careful attention to early termination and minimal resource consumption.

Imagine you have a big basket full of word cards. The goal is to find how many letters at the very start of every single card are exactly the same.

The code starts by looking at the first letter of every card. It has a little helper that keeps track of the current spot, starting at the beginning. It checks the card in the first position and then compares that letter to the same spot on every other card in the basket.

If any card is too short to reach that spot, or if the letter found there does not match the letter on the first card, the game stops right away. If every card has the same matching letter, the helper moves to the next spot to check the next letter. This process repeats over and over, moving one step forward each time until a difference is found or a card runs out of letters.

Once the team cannot find any more matching letters, it snips off that shared part from the front of the first card and shows that as the final answer.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java										TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java	C#	C	Rust	JS	Ruby		Go		PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend					C
	BigEggStudy				C#
	black-shadows	C++
	bujosa						Rust
	chandansgowda		Python
	charles-wangkai			Java
	chenyanzhe	C++
	Dijkstra-Edu			Java
	DimitrisJim					C
	everthis							JS
	fartem								Ruby
	FelixFan1122				C#
	fengvyi	C++
	fpdjsns	C++
	gaosq0604		Python
	Garvit244		Python
	gouthampradhan			Java
	halfrost										Go
	haoel	C++
	JoshCrozier							JS
	keineahnung2345	C++
	Krazune	C++
	lennylxx					C
	linouk23	C++
	lkwq007		Python
	luangong	C++
	pruthvikp		Python
	qiyuangong			Java
	ruoru						Rust
	Shamik07											Dart
	shreymehul				C#
	sonugiri1043	C++
	suxrobGM				C#
	varunu28			Java
	vli02					C
	vthwang			Java
	XiaotaoGuo	C++
	yuanliu666									Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, JavaScript, PHP, Python, Ruby, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
black-shadows	C++, C++
bujosa	Rust
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
FelixFan1122	C#
fengvyi	C++
fpdjsns	C++
gaosq0604	Python
Garvit244	Python
gouthampradhan	Java
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
lennylxx	C
linouk23	C++
lkwq007	Python
luangong	C++
pruthvikp	Python
qiyuangong	Java
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
XiaotaoGuo	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality