Abstract / Summary

Given a string and a character, find the position where the character first appears.

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 47% (9+ million submissions).

Typical patterns to solve this problem:

• String
• String Matching
• Two Pointers

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 provided implementation defines a class Solution with a single public member function strStr. The purpose of this function is to locate the first occurrence of the substring needle within the string haystack. It leverages the standard library’s std::string::find method to perform the search and directly returns the result as an integer.

Core Logic

The heart of the algorithm is a one-line call to find. The function receives two std::string parameters, haystack and needle, and forwards them to the library routine.

int strStr(string haystack, string needle) {
    return haystack.find(needle);
}

std::string::find scans haystack for the pattern needle and yields the index of the first match. If the pattern is not present, the function returns std::string::npos, which is a constant representing an invalid position. Because the return type of strStr is int, the npos value is implicitly converted to -1 when it does not fit within the range of a signed integer, thereby signaling “not found” in a conventional manner.

Edge Cases Handled

When needle is an empty string, the C++ standard specifies that find returns 0. This behavior aligns with the typical definition of substring search where an empty pattern is considered to be found at the start of any string. The implementation therefore correctly returns 0 for this scenario without any additional checks.

If needle is longer than haystack, find immediately determines that a match is impossible and returns npos. The conversion to int yields -1, indicating the absence of the substring.

When needle does not occur anywhere inside haystack, find again returns npos. The conversion to int produces -1, providing a clear sentinel value for “not found”.

The function also gracefully handles strings that contain embedded null characters because std::string stores size information separately from the character data. The find method operates on the stored length, so embedded nulls do not prematurely terminate the search.

Performance Optimizations

By delegating the search to std::string::find, the implementation benefits from the highly tuned algorithms present in the standard library. Modern C++ libraries often employ advanced techniques such as two-way string matching, Boyer-Moore-Horspool, or SIMD-accelerated scans, depending on the length of the pattern and the characteristics of the input. These internal optimizations are applied automatically without any extra code.

The direct return of the result avoids additional copying or temporary variables, keeping the call overhead minimal. The function signature passes the strings by value, which may trigger move semantics when the arguments are rvalues, reducing unnecessary allocations.

Overall, the code achieves an efficient search by relying on the standard library’s internal mechanisms, which are continuously refined by compiler and library maintainers.

Imagine a giant box filled with blocks, where each block has a letter written on it in a long, straight row. This row of blocks is called a haystack. There is also a smaller group of blocks called a needle. The goal is to find where that small group of blocks first appears inside the long row. The code uses a special, fast tool built into the computer to look through the haystack. It slides along the row of blocks, checking if the group matches the needle. As soon as it spots the needle, it points to the very first block where the match begins. If the needle is not inside the haystack at all, it simply says that it could not be found.

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#	Rust	JS	Go					PHP	TS
	LeetcodeHelp	C++	Python	Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python	Java
github	aylei						Rust
	begeekmyfriend				C
	BigEggStudy					C#
	chandansgowda		Python
	charles-wangkai			Java
	Dijkstra-Edu			Java
	DimitrisJim				C
	everthis							JS
	fartem										Ruby
	fengvyi	C++
	gaosq0604		Python
	halfrost								Go
	JoshCrozier							JS
	lennylxx				C
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	martianoff									Scala
	muhammadfarhankt								Go
	pruthvikp		Python
	qiyuangong		Python
	ruoru						Rust
	Shamik07												Dart
	shreymehul					C#
	sonugiri1043	C++
	suxrobGM					C#
	varunu28			Java
	vli02				C
	vthwang			Java
	wisdompeak	C++
	XiaotaoGuo	C++
	yuanliu666											Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
BigEggStudy	C#
chandansgowda	Python
charles-wangkai	Java
Dijkstra-Edu	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fengvyi	C++
gaosq0604	Python
halfrost	Go
JoshCrozier	JavaScript
lennylxx	C
linouk23	C++
lkwq007	Python
MacJim	C++
martianoff	Scala
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Python
ruoru	Rust
Shamik07	Dart
shreymehul	C#
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
vthwang	Java
wisdompeak	C++
XiaotaoGuo	C++
yuanliu666	Kotlin
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