First Unique Character in a String - Leet Code Solution
September 08, 2020
Problem Statement
Given a string, find the first non-repeating character in it and return its index. If it doesn’t exist, return -1.
Example
s = "leetcode"
return 0.
s = "loveleetcode"
return 2.
Note: You may assume the string contains only lowercase English letters.
Solution Brute Force
Lets take a look at the simple solution.
- Have two loops. first will iterate till length of string
- in second loop, iterate from beginning to end.
- And check if the character is found anywhere
- We can keep track of duplicate found by a boolean flag
- And if during our inner loop, if we found that character is not found. This is our answer
Code
public int firstUniqChar_bruteforce(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;
}
Complexity
Its O(n^2)
Another Solution using a HashMap
- Iterate over string, and keep track of count of each character
- Maintain a
HashMap<Character, Integer>
- Now, iterate over string again
- For each character, lookup in our
HashMap
- If the count of that character is only
1
, this is our answer - Since,
1
means this character is in the string only 1 times.
Code
public int firstUniqChar(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (int i=0; i<s.length(); i++) {
int count = map.getOrDefault(s.charAt(i), 0);
count ++;
map.put(s.charAt(i), count);
}
for (int i=0; i<s.length(); i++) {
if (map.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
Complexity
Its O(n)
Similar Posts
List of Sorting Algorithms
This topic is one of the most common studied. When somebody started preparation…
Magical usage of Bitwise operators - Get optimized solutions for many arithmatic problems
Introduction I will list some of the interesting usage of bitwise operators…
Three Sum Closest - Leet Code Solution
Problem Statement Given an array nums of n integers and an integer target, find…
System Design Interview Vocabulary Notes
In this post, we will see some of the frequently used concepts/vocabulary in…
Valid Palindrome - Leet Code Solution
Problem Statement Given a string, determine if it is a palindrome, considering…
Latest Posts
Authenticating Strapi backend with Next.js and next-auth using credentials and jwt
Introduction Strapi is a backend system provides basic crud operations with…
How to create Repository using Github Rest API, Configure Visibility and Assign a Team as Readonly
Introduction I had to create many repositories in an Github organization. I…
How to Download multiple Youtube Videos using Nodejs and Show a Progress Bar
Introduction I was trying to download some youtube videos for my kids. As I have…
Python - Some useful Pytest Commands
Introduction In this post, we will explore some useful command line options for…
Python - How to apply patch to Python and Install Python via Pyenv
Introduction In this post, we will see how we can apply a patch to Python and…
How to Install packages from command line and Dockerfile with Chocolatey
Introduction We will introduce a Package Manager for Windows: . In automations…