Problem 387

Abstract / Summary

Find the first character in a string that appears only once.

Note

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

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
9 lines | 253 bytes | submitted August 13, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 66% (3+ million submissions).

Typical patterns to solve this problem:
  • Counting
  • Hash Table
  • Queue
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.93 | σ = 1.41

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

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 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++
56 links | 40 authors | 11 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

12 easy
13 solutions   August 13, 2023

Extra

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