387. First Unique Character in a String
Problem Description
The problem provides us with a string s
and our task is to find the first character in this string that does not repeat anywhere else within that same string. In other words, we need to identify a character that appears only once in the string, and then return the position (index) of that character in the string. If our string doesn't have any non-repeating characters, we must return -1
. An important detail is that we're interested in the first non-repeating character, so we must scan the string from the beginning, and as soon as we find a unique character, we know that is the answer.
Intuition
The intuition behind this solution starts with recognizing that in order to determine whether a character is repeated, we need to check the entire string. We can do this efficiently by counting how many times each character appears in the string. The Counter
class from Python's collections
module is a perfect fit for this, as it enables us to create a count of all characters with just a single pass through the string.
Once we have the counts of each character stored in the cnt
dictionary, we make another pass through the string. This time, we examine each character and consult the count we've stored in cnt
to see if it is 1
(which means the character is unique). The first time we find a character with a count of 1
, we know we've located the first non-repeating character, so we return its index.
If we get through the entire string without finding a non-repeating character, we return -1
, which signals that there aren't any unique characters in the string.
Learn more about Queue patterns.
Solution Approach
The provided solution utilizes two key components of the Python language: the Counter
class from the collections
module and the enumerate
function.
Here's a breakdown of how the solution is implemented:
-
cnt = Counter(s)
: TheCounter
class is used to create a dictionary-like object where each key is a character from the strings
, and the corresponding value is the number of times that character appears ins
. This is our first pass through the string and is done inO(n)
time complexity, wheren
is the length of the string. -
for i, c in enumerate(s)
: We then use Python's built-inenumerate
function to iterate overs
again. This time,enumerate
gives us both the indexi
and the characterc
for each position in the string. We do this to be able to return the index of the first unique character we encounter. -
if cnt[c] == 1
: Within the loop, we check the count of the current characterc
by accessing it in our countercnt
. If the count is1
, it meansc
is a non-repeating character, and since we are scanning from the start of the string, it is the first non-repeating character. -
return i
: When we find a character that appears only once, we return the indexi
. This is our desired result according to the problem description. -
return -1
: This line is reached only if the loop completes without returning an index, indicating that there are no characters in the string that are non-repeating. Therefore, we return-1
as specified.
The overall time complexity of the solution is O(n)
as we traverse the string twiceāonce for counting the characters and once for checking their uniqueness. The space complexity is also O(n)
because in the worst-case scenario, the Counter
object may hold a distinct count for every character if they are all unique.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose the input string s
is "leetcode"
.
- We use the
Counter
to count the occurrences of each character ins
. TheCounter(s)
would look like this:
Counter({'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1})
-
We then iterate over the string
s
with the help ofenumerate
which gives us the index and the character at that index. Our first iteration would give us index0
and character'l'
. -
We then check if the count of the current character in the
cnt
dictionary is1
. For this example,cnt['l']
would be1
. -
Since the count is
1
, we have found our first non-repeating character, which is'l'
. -
We return the index of
'l'
, which is0
.
This works correctly for our example. If our string was "lleetcode"
, where the first 'l'
is not unique, the steps would be as follows:
- The
Counter
for this string would be:
Counter({'l': 2, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1})
-
Iterating through the string, when we reach the character
't'
at index2
, we would find thatcnt['t']
is1
, which means't'
is the first non-repeating character. -
We would return
2
, which is the index of't'
.
Following these steps ensures we find the first unique character efficiently, or determine that there isn't one if we reach the end of the string without finding any character with a count of 1
.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def firstUniqChar(self, s: str) -> int:
5 # Create a counter object to count the frequency of each character in the string
6 char_count = Counter(s)
7
8 # Iterate over the characters in the string with their indices
9 for index, char in enumerate(s):
10 # If the character's count is 1, it is unique
11 if char_count[char] == 1:
12 # Return the current index as the first unique character's position
13 return index
14
15 # If no unique character is found, return -1
16 return -1
17
1class Solution {
2 public int firstUniqChar(String s) {
3 // Create an array to store the frequency of each character
4 int[] charCounts = new int[26];
5
6 // Get the length of the string for use in loops
7 int stringLength = s.length();
8
9 // Iterate over the string to count the frequency of each character
10 for (int i = 0; i < stringLength; ++i) {
11 charCounts[s.charAt(i) - 'a']++;
12 }
13
14 // Iterate over the string a second time to find the first unique character
15 for (int i = 0; i < stringLength; ++i) {
16 // If the count of the current character is 1, return its index
17 if (charCounts[s.charAt(i) - 'a'] == 1) {
18 return i;
19 }
20 }
21
22 // If no unique character is found, return -1
23 return -1;
24 }
25}
26
1#include <string> // Include string library for string type
2
3class Solution {
4public:
5 // Function to find the first non-repeating character in a string
6 // and return its index. If it doesn't exist, return -1.
7 int firstUniqChar(std::string s) {
8
9 // Initialize a count array with 26 elements for each alphabet character
10 int charCount[26] = {0};
11
12 // Iterate over each character in the string and
13 // increment the count in the corresponding array index
14 for (char c : s) {
15 ++charCount[c - 'a'];
16 }
17
18 // Get the size of the string
19 int strLength = s.size();
20
21 // Iterate over the string once again
22 for (int i = 0; i < strLength; ++i) {
23 // If the count at the position of the character is 1,
24 // it means that it is a unique character, so return its index
25 if (charCount[s[i] - 'a'] == 1) {
26 return i;
27 }
28 }
29
30 // If no unique character is found, return -1
31 return -1;
32 }
33};
34
1function firstUniqChar(s: string): number {
2 // Create an array to keep track of the frequency of each character.
3 const charFrequency = new Array(26).fill(0);
4
5 // Iterate through the string to fill the frequency array.
6 for (const character of s) {
7 // Increment the frequency of the character in the array.
8 // 'a'.charCodeAt(0) gives us the char code for 'a', which we subtract
9 // from the current char code to get the index (assuming lowercase ASCII).
10 charFrequency[character.charCodeAt(0) - 'a'.charCodeAt(0)]++;
11 }
12
13 // Iterate through the string to find the first unique character.
14 for (let index = 0; index < s.length; index++) {
15 // Check if the character at 'index' has a frequency of 1,
16 // which means it's unique.
17 if (charFrequency[s.charCodeAt(index) - 'a'.charCodeAt(0)] === 1) {
18 // If the character is unique, return its index.
19 return index;
20 }
21 }
22
23 // If there is no unique character in the string, return -1.
24 return -1;
25}
26
Time and Space Complexity
Time Complexity
The time complexity of the given code has two main components: one for creating the counter dictionary, and the other for iterating through the string.
-
Counter(s)
: This function creates a hashmap (dictionary) of character frequencies in the strings
. The time complexity of this operation isO(n)
as it requires going through all the characters in the string once, wheren
is the length of the string. -
for i, c in enumerate(s)
: This loop iterates over each character index pair in the string to check if the character count is 1. The iteration itself isO(n)
, since it goes over each character of the string once.
The combined time complexity is the sum of these two operations, which are both linear with respect to the length of the input string. Therefore, the overall time complexity is O(n)
.
Space Complexity
The space complexity of the given code is primarily dependent on the size of the counter dictionary that gets created.
Counter(s)
: The space occupied by this dictionary is proportional to the number of distinct characters in the strings
. In the worst-case scenario, where all characters in the string are unique, the space required will beO(n)
. However, for a string with a fixed character set (like the ASCII characters), the space complexity would beO(1)
with respect to the size of the character set since the counter dictionary cannot exceed the size of the character set irrespective of the length of the string.
Combining the above, the worst-case space complexity of the code is O(n)
if the number of distinct characters is proportional to the length of the string. For strings in a fixed character set, the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!