Selection Sort Algorithm
It is one of a simple algorithm to study for a beginner to understanding sorting…
September 08, 2020
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.
Lets take a look at the simple solution.
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;
}
Its O(n^2)
HashMap<Character, Integer>
HashMap
1
, this is our answer1
means this character is in the string only 1 times.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;
}
Its O(n)
It is one of a simple algorithm to study for a beginner to understanding sorting…
Graph Topological Sorting This is a well known problem in graph world…
This problem is a simple mathematical calculation. Lets start deriving some…
Problem Statement Given an array of integers, find if the array contains any…
Max Priority Queue is a data structure which manage a list of keys(values). And…
Problem Statement Given a string s, return the maximum number of unique…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…