First Unique Character in a String
First Unique Character in a String is a easy arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (count, then scan), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (compare against every other position) up.
Problem
Given a string s, find the first character that occurs exactly once in it and return its index. If every character appears more than once, return -1.
Examples
Example 1
- Input
s = "swiss"- Output
1- Why
- 's' appears three times; 'w' at index 1 appears once and comes before the other unique letter 'i'.
Example 2
- Input
s = "noon"- Output
-1- Why
- Both 'n' and 'o' appear twice, so no character is unique.
Example 3
- Input
s = "tactic"- Output
1- Why
- 't' and 'c' repeat; 'a' at index 1 is the first character that occurs exactly once.
Constraints
1 <= s.length <= 10^5scontains only lowercase English letters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (compare against every other position) | O(n²) | O(1) |
| Optimal (count, then scan) | O(n) | O(1) |
1Brute force (compare against every other position)
O(n²)Each of the n positions may scan the other n - 1 positions.O(1)Only loop variables.For each index i, scan the whole string for another index with the same character. The first i with no match is the answer.
- For i from 0 to n - 1: set unique = true.
- For j from 0 to n - 1, j != i: if s[j] == s[i], unique = false and stop.
- If unique, return i. After the loop, return -1.
class Solution {
public int firstUniqChar(String s) {
int n = s.length();
for (int i = 0; i < n; i++) {
boolean unique = true;
for (int j = 0; j < n; j++) {
if (j != i && s.charAt(j) == s.charAt(i)) {
unique = false;
break;
}
}
if (unique) return i;
}
return -1;
}
}class Solution:
def firstUniqChar(self, s: str) -> int:
n = len(s)
for i in range(n):
unique = True
for j in range(n):
if j != i and s[j] == s[i]:
unique = False
break
if unique:
return i
return -1class Solution {
public:
int firstUniqChar(string s) {
int n = s.size();
for (int i = 0; i < n; i++) {
bool unique = true;
for (int j = 0; j < n; j++) {
if (j != i && s[j] == s[i]) {
unique = false;
break;
}
}
if (unique) return i;
}
return -1;
}
};function firstUniqChar(s) {
const n = s.length;
for (let i = 0; i < n; i++) {
let unique = true;
for (let j = 0; j < n; j++) {
if (j !== i && s[j] === s[i]) {
unique = false;
break;
}
}
if (unique) return i;
}
return -1;
}2Optimal (count, then scan)
O(n)Two linear passes over the string.O(1)The count array has a fixed size of 26, independent of n.Two passes. The first pass counts how often each of the 26 letters appears. The second pass walks the string from the left and returns the first index whose letter has a count of exactly 1.
- count = int[26]; for each c in s: count[c - 'a']++.
- For i from 0 to n - 1: if count[s[i] - 'a'] == 1, return i.
- Return -1.
class Solution {
public int firstUniqChar(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
if (count[s.charAt(i) - 'a'] == 1) return i;
}
return -1;
}
}class Solution:
def firstUniqChar(self, s: str) -> int:
count = [0] * 26
for c in s:
count[ord(c) - ord("a")] += 1
for i, c in enumerate(s):
if count[ord(c) - ord("a")] == 1:
return i
return -1class Solution {
public:
int firstUniqChar(string s) {
int count[26] = {0};
for (char c : s) count[c - 'a']++;
for (int i = 0; i < (int)s.size(); i++) {
if (count[s[i] - 'a'] == 1) return i;
}
return -1;
}
};function firstUniqChar(s) {
const count = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) count[s.charCodeAt(i) - 97]++;
for (let i = 0; i < s.length; i++) {
if (count[s.charCodeAt(i) - 97] === 1) return i;
}
return -1;
}Edge cases to test
- A single character: index 0
- Every character repeated: -1
- The only unique character is the last one
- All 26 letters once: index 0
Hints
Hint 1
A character is unique if its total count in the string is 1. Can you know every count before deciding?
Hint 2
Count with an array of 26 integers in one pass, then scan the string again and return the first index whose letter has count 1.
FAQ
What is the best time complexity for First Unique Character in a String?
Optimal (count, then scan) runs in O(n) time and O(1) extra space. Two linear passes over the string.
Which pattern does First Unique Character in a String use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, Number of Matching Subsequences, Group Shifted Strings.
Is there a brute force solution for First Unique Character in a String?
Yes. Brute force (compare against every other position) takes O(n²) time and O(1) space. For each index i, scan the whole string for another index with the same character.
Which edge cases should I test for First Unique Character in a String?
A single character: index 0; Every character repeated: -1; The only unique character is the last one; All 26 letters once: index 0.