Intro: I am a former accountant turned software engineer graduated from coding bootcamp. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.
Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. Here is my approach:
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- Combat the forgetting curve: Re-do the question for the next three days. And come back regularly to revisit the problem.
387. First Unique Character in a String
Difficulty: Easy
Language: JavaScript
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
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
Constraints:
1 <= s.length <= 105
-
s
consists of only lowercase English letters.
Solution 1 (Hashmap):
var firstUniqChar = function(s) {
let hash = {}
//Intialize a hash table (note 6) that allows us to save data as
//such: {character1:count1, character2:count2, character3:count3}
for(let i = 0; i < s.length; i++){
//Loop (note 1) through string 's' and save character and count
//into the hashtable created above
hash[s.charAt(i)]? hash[s.charAt(i)]++ : hash[s.charAt(i)] = 1
//if such character exist, increase count by 1, if not (note 7),
//let count equal to 1. 's.charAt(i)' gives us the
//character at index i and 'hash[character]' will point to the
//count of that character.
}
for(let i = 0; i < s.length; i++){
//Loop (note 1) through the string once more time to identify the
//count for each letter that is now stored in 'hash'
if(hash[s.charAt(i)] == 1) return i
//if (note3)count of character at (note 4) index i has count equal
//(note5) to 1, return the index. 's.charAt(i)' gives us the
//character at index i and 'hash[character]' will point to the
//count of that character.
}
return -1
//if such index doesn't exist, return -1
};
Solution 2 :
var firstUniqChar = function(s) {
for(i=0; i<s.length; i++)
//Loop (note 1) through string 's' and see if there is more than
//once index for a character.
if(s.indexOf(s[i])===s.lastIndexOf(s[i])) return i
//if the first index (note 7) and last index (note 8) found for a
//character is the same, that means this character is unique. If
//this character is found at more than one index, there are
//duplicates of this character in the string.
return -1
//if such index doesn't exist, return -1
};
References:
LeetCode Problem Link
LeetCode Discussion: miryang
Note 1: Loop and Iteration
Note 2: Addition assignment (+=)
Note 3: if...else
Note 4: String.prototype.charAt()
Note 5: Equality (==)
Note 6: JS Hash Table
Note 7: Ternary Operator
Note 8: Array.indexOf()
Note 9: Array.lastindexOf()
Blog Cover Image Credit
Top comments (0)