Find the First Non-Repeating Character in a String

Easy10–15 min

Topics

StringHash Table

Companies

AmazonMicrosoftBloomberg

Given a string s, find the first character that never repeats anywhere else in the string, and return its index. If every character repeats, return -1. Checking each character against every other character works, but it's quadratic. The faster approach counts every character's frequency in one pass, then makes a second pass in order and returns the index of the first character whose frequency is exactly 1 — the first one that was never seen again.

Test Case 1:

Input:s = "swiss"

Output:1

Explanation:'s' appears 3 times, but 'w' at index 1 appears only once — it's the first non-repeating character.

Test Case 2:

Input:s = "aabb"

Output:-1

Explanation:Every character repeats — there's no non-repeating character.

Test Case 3:

Input:s = "leetcode"

Output:0

Explanation:'l' at index 0 never repeats anywhere else in the string.

Constraints

◆1 ≤ s.length ≤ 10⁵
◆s consists only of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (string) — 1-10 lowercase letters

1	class Solution {
2	public int firstUniqChar(String s) {
3	Map<Character, Integer> freq = new HashMap<>();
4	for (char c : s.toCharArray()) {
5	freq.put(c, freq.getOrDefault(c, 0) + 1);
6	}
7	for (int i = 0; i < s.length(); i++) {
8	if (freq.get(s.charAt(i)) == 1) return i;
9	}
10	return -1;
11	}
12	}
13

String

↑i

HashMap

s→1

Variables

cs

freq[c]1

UPDATE

s[0] = 's' — freq['s'] becomes 1.

Step 1 / 7

Approach & Solutions

Brute Force — Check Every Character Against the Rest

Brute

For each character, scan the entire rest of the string to check whether it appears again. The first character that matches nothing else is the answer. Simple, but comparing every character against every other character is quadratic.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int firstUniqChar(String s) {
        for (int i = 0; i < s.length(); i++) {
            boolean unique = true;
            for (int j = 0; j < s.length(); j++) {
                if (i != j && s.charAt(i) == s.charAt(j)) {
                    unique = false;
                    break;
                }
            }
            if (unique) return i;
        }
        return -1;
    }
}

Optimal — Frequency Map, Two Passes

Optimal

Count every character's frequency in one pass. Then scan the string a second time, in order, and return the index of the first character whose frequency is exactly 1. Since the alphabet is fixed (26 lowercase letters), the map holds at most 26 entries — effectively constant space.

TimeO(n)