Python 0387.py
class Solution:
def firstUniqChar(self, s: str) -> int:
freq = defaultdict(int)
for a in s:
freq[a] += 1
for a in range(len(s)):
if freq[s[a]] == 1:
return a
return -1
Difficulty
and has an acceptance rate of about 66% (3+ million submissions).
Typical patterns to solve this problem:
- Counting
- Hash Table
- Queue
- String
AI Disclaimer
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.
Code Walkthrough
Overview
The provided implementation defines a class Solution with a method firstUniqChar that receives a string s and returns the index of the first character that appears exactly once in the string. If no such character exists, the method returns -1. The algorithm proceeds in two distinct phases: counting character frequencies and scanning for the first unique occurrence.
Key Steps
The first phase builds a frequency map using a defaultdict from the collections module. Each character in the input string increments its associated counter.
freq = defaultdict(int)
for a in s:
freq[a] += 1
The second phase iterates over the string by index, checking the previously built frequency map. The moment a character with a count of 1 is encountered, its index is returned.
for a in range(len(s)):
if freq[s[a]] == 1:
return a
If the loop completes without finding a unique character, the method falls back to the sentinel value -1.
return -1
Edge Cases Handled
The algorithm gracefully handles an empty input string. In that scenario, the frequency map remains empty, the index loop does not execute, and the method directly returns -1, indicating the absence of a unique character.
When the string consists entirely of repeated characters, the frequency map records counts greater than one for each symbol. The subsequent scan never satisfies the condition freq[s[a]] == 1, leading again to the final -1 return.
Strings containing a mixture of unique and repeated characters are processed correctly because the frequency map captures the exact count for every symbol before the index scan begins. The first index that meets the uniqueness criterion is returned, ensuring that the earliest qualifying character is selected even if later characters are also unique.
Performance Optimizations
The implementation leverages defaultdict(int) to avoid explicit existence checks when updating the frequency map. This choice eliminates conditional branches inside the counting loop, allowing the interpreter to perform a simple increment operation for each character.
By separating the counting and scanning phases, the code ensures that each character of the input string is visited exactly twice-once for counting and once for locating the unique character. This deterministic two-pass approach avoids nested loops or repeated lookups that could increase the number of operations.
The use of direct index access (s[a]) during the second pass avoids the overhead of enumerating over characters while still needing the index for the return value. This direct indexing aligns with the underlying string storage, providing fast retrieval without additional iterator objects.
Overall, the design balances clarity with efficient use of Python’s built-in data structures, resulting in a solution that processes the input with minimal overhead while maintaining straightforward logic.
ELI5 - Simplified Explanation
Imagine having a long string of colorful building blocks lined up in a row. Some colors appear many times, but a few lucky colors only appear exactly once.
The code starts by walking through the whole line of blocks. It carries a sticky notepad to keep track of how many times each color shows up. Every time a block is picked up, a mark is made on the notepad for that color to keep a tally.
Once the notepad is finished and full of counts, the code goes back to the very front of the line. It looks at the first block and checks the notepad to see what the count is for its color. If the notepad says that color only appears once, the search stops right there and points to that block. If the count is higher than one, the code moves to the next block and checks again until it finds that special lonely block that never repeats. If it walks through the entire line and never finds one that appears solo, it just quietly gives up.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
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 | JS | Go | PHP | TS | |||||
| LeetcodeHelp | C++ | Python | Java | |||||||||
| MemoryLimitExceeded | C++ | Python | ||||||||||
| Progiez | C++ | Python | Java | |||||||||
| github | BigEggStudy | C# | ||||||||||
| black-shadows | C++ | |||||||||||
| charles-wangkai | Java | |||||||||||
| chenyanzhe | C++ | |||||||||||
| Dijkstra-Edu | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JS | |||||||||||
| fartem | Ruby | |||||||||||
| FelixFan1122 | C# | |||||||||||
| fpdjsns | C++ | |||||||||||
| fsq | Python | |||||||||||
| Garvit244 | Python | |||||||||||
| gouthampradhan | Java | |||||||||||
| halfrost | Go | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JS | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| muhammadfarhankt | Go | |||||||||||
| pruthvikp | Python | |||||||||||
| qiyuangong | Java | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| trung-hn | Python | |||||||||||
| varunu28 | Java | |||||||||||
| vli02 | C | |||||||||||
| vthwang | Java | |||||||||||
| XiaotaoGuo | C++ | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ | |||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||
| WalkCCC | C++, Python, Java | |||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, PHP, Python, TypeScript | |||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||
| MemoryLimitExceeded | Python, C++ | |||||||||||
| Progiez | C++, Java, Python | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++, C++ | |||||||||||
| charles-wangkai | Java | |||||||||||
| chenyanzhe | C++ | |||||||||||
| Dijkstra-Edu | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JavaScript | |||||||||||
| fartem | Ruby | |||||||||||
| FelixFan1122 | C# | |||||||||||
| fpdjsns | C++ | |||||||||||
| fsq | Python | |||||||||||
| Garvit244 | Python | |||||||||||
| gouthampradhan | Java | |||||||||||
| halfrost | Go | |||||||||||
| haoel | C++ | |||||||||||
| JoshCrozier | JavaScript | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| muhammadfarhankt | Go | |||||||||||
| pruthvikp | Python | |||||||||||
| qiyuangong | Java | |||||||||||
| ruoru | Rust | |||||||||||
| shreymehul | C# | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| trung-hn | Python | |||||||||||
| varunu28 | Java | |||||||||||
| vli02 | C | |||||||||||
| vthwang | Java | |||||||||||
| XiaotaoGuo | C++ | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 451: Sort Characters By Frequency
- problem 2351: First Letter to Appear Twice
Solved On The Same Day
- problem 342: Power of Four
- problem 344: Reverse String
- problem 345: Reverse Vowels of a String
- problem 349: Intersection of Two Arrays
- problem 350: Intersection of Two Arrays II
- problem 412: Fizz Buzz
- problem 414: Third Maximum Number
- problem 434: Number of Segments in a String
- problem 448: Find All Numbers Disappeared in an Array
- problem 485: Max Consecutive Ones
- problem 504: Base 7
- problem 507: Perfect Number
Extra
- 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