First Unique Character DSA Solution - Study Chapter | QuizMaker

First Unique Character explained with O(n^2) brute force, optimized frequency map, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 12m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 9: Hashing & Prefix Sum

Learning Outcome

After this lesson, you should be able to count characters first and then preserve order with a second pass.

Problem Statement

Given a string, return the index of its first non-repeating character, or -1 if none exists.

Input	Output	Why
`s = "leetcode"`	`0`	The character l appears once and is the first unique character.

Brute Force Approach

For each character, scan the entire string to count it. This repeats work.

Optimized Approach

Build a frequency table once. Then scan the string in original order and return the first index with frequency 1.

Exact Pseudocode

freq = character counts
for i from 0 to length(s) - 1:
  if freq[s[i]] == 1:
    return i
return -1

Reference Code

class Solution:
    def firstUniqChar(self, s):
        freq = {}
        for ch in s:
            freq[ch] = freq.get(ch, 0) + 1

        for i, ch in enumerate(s):
            if freq[ch] == 1:
                return i

        return -1

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> freq(26, 0);
        for (char c : s) freq[c - 'a']++;

        for (int i = 0; i < s.size(); i++) {
            if (freq[s[i] - 'a'] == 1) return i;
        }

        return -1;
    }
};

class Solution {
    public int firstUniqChar(String s) {
        int[] freq = new int[26];
        for (char c : s.toCharArray()) freq[c - 'a']++;

        for (int i = 0; i < s.length(); i++) {
            if (freq[s.charAt(i) - 'a'] == 1) return i;
        }

        return -1;
    }
}

Sample Dry Run

Step	State	Result
Count	l:1, e:3, t:1, c:1, o:1, d:1	Frequency table ready
Index 0	l has count 1	Return 0
No need	Later unique chars exist	First unique is already found

Complexity

Measure	Value	Reason
Time	O(n)	The string is scanned twice.
Space	O(1)	For lowercase English letters, the frequency array has fixed size.

Edge Cases

If no unique character exists, return -1.
Return the first unique by original index, not by map order.
If the character set is larger, use a hashmap instead of size 26.

Interview Checklist

Count first, then scan in original order.
Do not return the first map key with count 1.
Match the frequency structure to the character set.

FAQs

Why two passes?

The first pass learns all counts. The second pass preserves the original order.

Why not sort the string?

Sorting loses the original index order required by the problem.

What is the core pattern?

Frequency map plus order-preserving scan.