Solution: First Non-repeating Character (easy)

Problem Statement

Given a string, identify the position of the first character that appears only once in the string. If no such character exists, return -1.

Examples

Example 1:
- Input: "apple"
- Expected Output: 0
- Justification: The first character 'a' appears only once in the string and is the first character.
Example 2:
- Input: "abcab"
- Expected Output: 2
- Justification: The first character that appears only once is 'c' and its position is 2.
Example 3:
- Input: "abab"
- Expected Output: -1
- Justification: There is no character in the string that appears only once.

Constraints:

1 <= s.length <= 10<sup>5</sup>
s consists of only lowercase English letters.

Why this is a Hash Maps problem

What the question says	The signal it matches
"identify the position of the first character that appears only once"	the question says first and only, which are counting words
a character qualifies on how many times it appears	you need to count how often things appear, then act on those counts
comparing every character against every other to see if it repeats	your first idea is a nested loop that recounts the same thing

Counting first and then re-reading the string in order is the count, then re-read the input in order variant.

The closest alternative. The word first is what forces two passes. A single pass cannot know whether a character repeats later. The counts have to be complete before any answer is given.

Then the original string is read again. The map does not record the order the characters arrived in.

Solution

To solve this problem, we'll use a hashmap to keep a record of each character in the string and the number of times it appears. First, iterate through the string and populate the hashmap with each character as the key and its frequency as the value. Then, go through the string again, this time checking each character against the hashmap. The first character that has a frequency of one (indicating it doesn't repeat) is your target. This character is the first non-repeating character in the string. If no such character exists, the solution should indicate that as well. This two-pass approach ensures efficiency, as each character is checked against a pre-compiled frequency map.

Initialization: Begin by creating a hashmap to store the frequency of each character in the string. This hashmap will help in identifying characters that appear only once.
Frequency Count: Traverse the string from the beginning to the end. For each character, increment its count in the hashmap.
First Unique Character: Traverse the string again from the beginning. For each character, check its frequency in the hashmap. If the frequency is 1, return its position as it's the first unique character.
No Unique Character: If the string is traversed completely without finding a unique character, return -1.

Using a hashmap ensures that we can quickly determine the frequency of each character without repeatedly scanning the string.

Algorithm Walkthrough

a is new, so it goes into the map with a count of 1. Each item is read once and stored once. Nothing is searched for.

1 of 10

Code

Here is the code for this algorithm:

Python3

. . . .

Time Complexity

Populating the hashmap with frequencies: We traverse the entire string once to populate the hashmap with the frequency of each character. This operation takes $O(n)$ time, where n is the length of the string.
Finding the first unique character: We traverse the string again to find the first character with a frequency of 1. This operation also takes $O(n)$ time.

Given that these two operations are sequential and not nested, the overall time complexity is $O(n) + O(n)$ , which simplifies to $O(n)$ .

Space Complexity

Hashmap for frequencies: In the worst case, every character in the string is unique. For a string with only lowercase English letters, the maximum number of unique characters is 26. However, if we consider all possible ASCII characters, the number is 128. If we consider extended ASCII, it's 256. In any case, this is a constant number. Therefore, the space complexity for the hashmap is $O(1)$ because it doesn't grow proportionally with the size of the input string.
Input string: The space taken by the input string is not counted towards the space complexity, as it's considered input space.

Given the above, the overall space complexity of the algorithm is $O(1)$ .

.....

Unlock this and all other premium problems.

No code editor for this lesson

This lesson focuses on concepts and theory