Lesson

8.10First Unique Character

Problem Statement

Find the first unique (non-repeating) character in a string.

Example Inputs

Input: "swiss"
- Output: "w"
Input: "character"
- Output: "h"
Input: "aabbccdde"
- Output: "e"
Input: "javascript"
- Output: "j"

JavaScript Method - Using Only String Methods

Approach

To find the first unique character, we can loop through the string and use .indexOf() and .lastIndexOf() to check if each character only appears once.

Steps

Loop through each character in the string.
For each character, use .indexOf(char) and .lastIndexOf(char) to check if it only appears once.
If a character's first and last index are the same, it's unique. Return it as the first unique character.
If no unique character is found, return null.

Time & Space Complexity

Time Complexity: O(n^2), because for each character, we perform index checks that are O(n) operations.
Space Complexity: O(1), as no extra data structure is needed.

Code Snippet

Dry Run

Example input: "swiss"

Loop through "swiss":
- s → indexOf(s) !== lastIndexOf(s)
- w → indexOf(w) === lastIndexOf(w) → unique, return "w"
Final output: "w"

Alternative Approach - Using a Frequency Map

Approach

We can first count the frequency of each character using an object, then loop through the string to find the first character with a frequency of 1.

Steps

Initialize an empty object frequency to store character counts.
Loop through the string to populate frequency with character counts.
Loop through the string again, checking each character's frequency in frequency.
Return the first character with a frequency of 1. If none, return null.

Time & Space Complexity

Time Complexity: O(n), as we iterate through the string twice.
Space Complexity: O(k), where k is the number of unique characters.

Code Snippet

Dry Run

Example input: "swiss"

First pass to build frequency:
- s → { s: 1 }
- w → { s: 1, w: 1 }
- i → { s: 1, w: 1, i: 1 }
- s → { s: 2, w: 1, i: 1 }
- s → { s: 3, w: 1, i: 1 }
Second pass to find first unique character:
- s → frequency is 3
- w → frequency is 1, return "w"
Final output: "w"

Complexity Analysis

JavaScript Method (Using String Methods)

Time Complexity: O(n^2)
Space Complexity: O(1)

Alternative Approach (Using Frequency Map)

Time Complexity: O(n)
Space Complexity: O(k)

Conclusion

Finding the first unique character can be achieved by either checking each character’s index positions or by using a frequency map. The frequency map provides an optimized approach with linear time complexity.

Previous Next