First Unique Character in a String solution and explanation
TCS
Deloitte
IBM
Google
9 more videos on this problem
First Unique Character in String | Easy - Leetcode387Shradha Khapra · 13:23 · 50K views
First unique character in a string | Leetcode #387Techdose · 4:58 · 46K views
First Unique Character in a String - Leetcode 387 - PythonNeetCodeIO · 4:35 · 39K views
First Unique Character in a String | LeetCode problem 387Technosage · 9:57 · 27K views
First unique character in a String | Study AlgorithmsNikhil Lohia · 9:56 · 13K views
LeetCode Tutorial 387. First Unique Character in a StringGoodTecher · 10:04 · 4K views
Leetcode | 387. First Unique Character in a String | Java SolutionDeveloper Docs · 6:37 · 3K views
Leetcode #387 - First Unique Character in a String (Solution)Algorithms Illustrator · 8:50 · 3K views
387 First Unique Character in a String LeetCode (Google Interview Question) JavaScriptdev alex · 4:18 · 886 views
First Unique Character in a String Javascript | 387. First Unique Character in a String LeetcodePersistent Programmer · 7:39 · 728 views
The problem
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Example 1:
Input: s = "leetcode"
Output: 0
Explanation:
The character 'l' at index 0 is the first character that does not occur at any other index.
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
Constraints:
1 <= s.length <= 105sconsists of only lowercase English letters.
Approach overview
Problem Overview: You receive a string s and must return the index of the first character that appears exactly once. If every character repeats, return -1. The challenge is identifying the first non‑repeating character while keeping the scan efficient.
Approach 1: Using a Frequency Map (O(n) time, O(n) space)
The standard solution counts how many times each character appears, then scans the string again to find the first character with frequency 1. Use a hash-based structure such as a dictionary or array counter. First pass: iterate through the string and increment counts in the frequency map. Second pass: iterate again and return the first index where the stored count equals 1.
This works because counting compresses the entire string into quick lookups. Each character check becomes an O(1) hash lookup. The total work is two linear scans, which gives O(n) time complexity and O(n) space for the frequency table. This approach relies heavily on hash tables and counting techniques commonly used in string problems.
Some implementations also maintain a queue of candidate indices while counting. As soon as a character’s frequency becomes greater than one, its index can be removed from the queue. The front of the queue always represents the current first unique candidate.
Approach 2: Two Iterations Without Hash Map (O(n²) time, O(1) space)
This method avoids extra memory by checking each character directly against the rest of the string. For every index i, iterate through the string and count how many times s[i] appears. If the count is exactly one, return i. If the character repeats, move to the next position and repeat the process.
The key idea is brute-force comparison. Because each character may trigger another full scan of the string, the worst-case complexity becomes O(n²). The advantage is constant extra memory (O(1)) since no map or auxiliary structure is used. This approach mainly demonstrates baseline reasoning when solving string problems.
Recommended for interviews: The frequency map solution is what interviewers expect. It demonstrates knowledge of hash-based counting and reduces the search to linear time. The brute-force approach still matters because it shows you understand the core requirement before optimizing. After stating the naive idea, move quickly to the O(n) counting strategy.
Approach 1: Approach 1: Using a Frequency Map
This approach employs a hash map to store the frequency of each character in the string. Then, by iterating through the string again, we can find the first character with a frequency of 1 and return its index. If no such character is found, we return -1.
def firstUniqChar(s: str) -> int:
freq = {}
for c in s:
freq[c] = freq.get(c, 0) + 1
for i, c in enumerate(s):
if freq[c] == 1:
return i
return -1
print(firstUniqChar("leetcode"))import java.util.HashMap;
public class FirstUniqueCharacter {
public static int firstUniqChar(String s) {
HashMap<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
if (freq.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
String s = "leetcode";
System.out.println(firstUniqChar(s));
}
}#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int firstUniqChar(string s) {
unordered_map<char, int> freq;
for (char c : s) {
freq[c]++;
}
for (int i = 0; i < s.size(); ++i) {
if (freq[s[i]] == 1) {
return i;
}
}
return -1;
}
int main() {
string s = "leetcode";
cout << firstUniqChar(s) << endl;
return 0;
}function firstUniqChar(s) {
let freq = {};
for (let i = 0; i < s.length; i++) {
let char = s[i];
freq[char] = (freq[char] || 0) + 1;
}
for (let i = 0; i < s.length; i++) {
if (freq[s[i]] === 1) {
return i;
}
}
return -1;
}
console.log(firstUniqChar("leetcode"));#include <stdio.h>
#include <string.h>
int firstUniqChar(char * s) {
int freq[26] = {0};
for (int i = 0; s[i] != '\0'; i++) {
freq[s[i] - 'a']++;
}
for (int i = 0; s[i] != '\0'; i++) {
if (freq[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
int main() {
char s[] = "leetcode";
printf("%d\n", firstUniqChar(s));
return 0;
}using System;
using System.Collections.Generic;
public class FirstUniqueCharacter {
public static int FirstUniqChar(string s) {
Dictionary<char, int> freq = new Dictionary<char, int>();
foreach (char c in s) {
if (freq.ContainsKey(c)) {
freq[c]++;
} else {
freq[c] = 1;
}
}
for (int i = 0; i < s.Length; i++) {
if (freq[s[i]] == 1) {
return i;
}
}
return -1;
}
public static void Main(string[] args) {
string s = "leetcode";
Console.WriteLine(FirstUniqChar(s));
}
}This Python solution uses a dictionary to store the frequency of each character in the string. It then looks for the first character with a frequency of 1 and returns its index.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Using Two Iterations Without Hash Map
This approach involves iterating through the input string two times without using any auxiliary space like a hash map or dictionary. In the first iteration, we use an array to count the occurrences of each character. In the second iteration, we check for the first character that appears only once by referring to the count array. We conclude by returning its index or -1 if no such character is found.
def firstUniqChar(s: str) -> int:
count = [0] * 26
for char in s:
count[ord(char) - ord('a')] += 1
for index, char in enumerate(s):
if count[ord(char) - ord('a')] == 1:
return index
return -1
print(firstUniqChar("loveleetcode"))public class FirstUniqueCharacter {
public static 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;
}
public static void main(String[] args) {
System.out.println(firstUniqChar("loveleetcode"));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int firstUniqChar(string s) {
vector<int> count(26, 0);
for (char c : s) {
count[c - 'a']++;
}
for (int i = 0; i < s.length(); ++i) {
if (count[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
int main() {
cout << firstUniqChar("loveleetcode") << endl;
return 0;
}function firstUniqChar(s) {
let count = Array(26).fill(0);
for (let char of s) {
count[char.charCodeAt(0) - 97]++;
}
for (let i = 0; i < s.length; i++) {
if (count[s.charCodeAt(i) - 97] === 1) {
return i;
}
}
return -1;
}
console.log(firstUniqChar("loveleetcode"));#include <stdio.h>
#include <string.h>
int firstUniqChar(char * s) {
int count[26] = {0};
for (int i = 0; s[i]; i++) {
count[s[i] - 'a']++;
}
for (int i = 0; s[i]; i++) {
if (count[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
int main() {
char s[] = "loveleetcode";
printf("%d\n", firstUniqChar(s));
return 0;
}using System;
public class FirstUniqueCharacter {
public static int FirstUniqChar(string s) {
int[] count = new int[26];
for (int i = 0; i < s.Length; i++) {
count[s[i] - 'a']++;
}
for (int i = 0; i < s.Length; i++) {
if (count[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
public static void Main(string[] args) {
Console.WriteLine(FirstUniqChar("loveleetcode"));
}
}This Python variant sets up a list of size 26 to manage character frequency tracking. A second iteration helps find the initial non-redundant character's index.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Counting
We use a hash table or an array of length 26 cnt to store the frequency of each character. Then, we traverse each character s[i] from the beginning. If cnt[s[i]] is 1, we return i.
If no such character is found after the traversal, we return -1.
The time complexity is O(n), where n is the length of the string. The space complexity is O(|\Sigma|), where \Sigma is the character set. In this problem, the character set consists of lowercase letters, so |\Sigma|=26.
function firstUniqChar(s: string): number {
const cnt = new Map<string, number>();
for (const c of s) {
cnt.set(c, (cnt.get(c) || 0) + 1);
}
for (let i = 0; i < s.length; ++i) {
if (cnt.get(s[i]) === 1) {
return i;
}
}
return -1;
}func firstUniqChar(s string) int {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for i, c := range s {
if cnt[c-'a'] == 1 {
return i
}
}
return -1
}class Solution {
/**
* @param String $s
* @return Integer
*/
function firstUniqChar($s) {
for ($i = 0; $i < strlen($s); $i++) {
$hashtable[$s[$i]]++;
}
for ($i = 0; $i < strlen($s); $i++) {
if ($hashtable[$s[$i]] == 1) {
return $i;
}
}
return -1;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using a Frequency Map | Time Complexity: O(n) |
| Approach 2: Using Two Iterations Without Hash Map | Time Complexity: O(n) |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map (Hash Table) | O(n) | O(n) | General case. Best performance and standard interview solution. |
| Two Iterations Without Hash Map | O(n²) | O(1) | Useful for demonstrating brute-force reasoning or when avoiding extra memory. |
Frequently asked questions
Is First Unique Character in a String easy or hard?
The problem is classified as Easy. The main concept is frequency counting using a hash table, which makes it a common early interview question for practicing string processing and basic data structures.
First Unique Character in a String Python/Java solution
In Python, use a dictionary or collections.Counter to count characters, then iterate through the string to find the first index with count 1. In Java, use a HashMap or an int array of size 26 to store frequencies and perform the same two-pass scan.
How to solve First Unique Character in a String in O(n)?
Count the frequency of each character using a hash map or fixed-size array. After building the counts, iterate through the string and return the first index where the frequency equals 1. Because each pass processes the string once, the total complexity remains O(n).
What is the best approach for First Unique Character in a String?
The most efficient approach uses a frequency map (hash table). First count how many times each character appears, then scan the string again to find the first character with frequency 1. This runs in O(n) time with O(n) space and is the standard interview solution.
Is First Unique Character in a String asked at Google/Amazon/Meta?
This problem or close variations appear in interviews at companies like Amazon, Microsoft, and Meta. It tests basic hash table usage, frequency counting, and string traversal, which are common patterns in coding interviews.
What data structure is used in First Unique Character in a String?
A hash table (dictionary or map) is typically used to store character frequencies. Some optimized variants also combine the map with a queue to track candidate indices for the first unique character during iteration.
What is the time complexity of First Unique Character in a String?
The optimal solution runs in O(n) time because the string is scanned twice: once to count character frequencies and once to locate the first unique character. Space complexity is O(n) for the frequency map, though it can be reduced to O(1) if the alphabet size is fixed (like lowercase English letters).