Search for a command to run...
Professional software engineer working at CoverMyMeds, an enterprise healthtech firm that ensures patients get access to the medication they need.
Primarily focused on backend and systems design through Ruby and Elixir, but experienced with JavaScript and all things frontend
Interested in learning and teaching the craft of software; technical or otherwise
Join me as I innovate by iterating!
Hey, you're back! Well, for this I'd use a simple two column array
BASIC code at https://forums.craigslist.org/?ID=326981539
I neglected to put a guard around that first For loop in case the string was empty, oops
Austin It's O(n) since it's one pass through the string and then one pass through the array whose size is constant no matter how big the string gets.
Bring it on! If I can't quickly solve it in BASIC, I probably could in 1983 8-bit Atari LOGO
Still more edits lol — If you're looking for some really crazy challenges, try some Knuth
Austin Hey, you still alive? Is this an actual leetcode problem? If so, I can't find it. I'm mainly tackling the hard problems in C (the closest thing to BASIC they have lol) but I figured I'd convert the BASIC solutions I posted back in 2023 to C and actually submit them
EDIT: Is it 387. First Unique Character in a String? Looks like it
The state of software and the internet is insane. Most websites are unfindable. Every Google search is dominated by SEO marketers. The internet has lost its beauty in the fiasco of widespread adoption and has been immensely over-capitalized. Apps can...
My origin story
Ever feel like you're juggling too many tasks, and constantly dropping the ball? I've been there. Let me share these secret weapons I wish I'd had in my arsenal sooner. Over the past few months, I've had a lot of different work to do. Juggling my job...
Today we're gonna take a stab at a Medium LeetCode problem. For a long time I never even attempted these because I was worried that they'd be "too hard", but this example will demonstrate that this is not the case. Join me as we dive into the problem...
If you're struggling with LeetCode problems, algorithms and data structures, or job interview prep, hash maps are a great tool to have in your tool belt. They're fast, flexible, and easy to implement. Other languages like Ruby utilize hashes specifically, but JavaScript has Objects for a similar effect.
Today we're going to solve the "First Non-Repeating Character" problem in O(n) time and space complexity, then dig into the details of how it all works.
Let's dive right in!
Write a function that takes in a string of lowercase English-alphabet characters and returns the index of the string's first non-repeating character.
The first non-repeating character is the first character in a string that occurs only once.
If the input string doesn't have any non-repeating characters, your function should return -1.
Sample Input
string = "abcdcaf"
Sample Output
1
The first non-repeating character is "b", and it is found at index 1.
We're going to want to iterate through the string and create a hashmap containing the character and its frequency.
This will look something like below, for our sample input:
{ "a": 2, "b": 1, "c": 2, "d": 1, "f": 1}
Now we have a hash containing our character:frequency pairs. If a character has a frequency greater than or equal to 2, we know that there are duplicates of that character in the string, so this entry should be deleted.
{ "b": 1, "d": 1, "f": 1 }
Now, using JavaScript's inbuilt Object methods, we should:
find the first character of the hash
find the index at which that character appears in the array
return the index
In this case, that would be 1 since "b" appears as the second character in the initial array.
This problem can be solved with a time and space complexity of O(n). Code and explanations below!
function firstNonRepeatingCharacter(string) {
let obj = {}
let split_str_arr = string.split("")
let makeKeys = (obj, str_arr) => {
for (let i = 0; i < str_arr.length; i++) {
char = str_arr[i]
if (obj[char]) {
obj[char] += 1
} else {
obj[char] = 1
}
}
}
let deleteDuplicateKeys = (obj) => {
for (var key in obj) {
if (obj.hasOwnProperty(key)) {
if(obj[key] >= 2) {
delete obj[key]
}
}
}
}
let first;
let answer;
let checkAnswer = (obj, str_arr) => {
if (Object.keys(obj).length > 0) {
first = Object.keys(obj)[0]
answer = str_arr.indexOf(first)
} else {
answer = -1
}
}
makeKeys(obj, split_str_arr)
deleteDuplicateKeys(obj)
checkAnswer(obj, split_str_arr)
return answer
}
Let's split this down, method-by-method.
makeKeys()
Iterate through the initial split string array and populates our obj hash with the string's character and its frequency of appearances within the string.
This will accomplish a state like:
{ "a": 2, "b": 1, "c": 2, "d": 1, "f": 1}
deleteDuplicateKeys()
Iterate through our hash map, checking first if the element exists within the hash using the hasOwnProperty method, then deleting any occurrences that have a frequency of 2 or higher.
{ "b": 1, "d": 1, "f": 1 }
checkAnswer()
Check if we have any remaining elements after deduplication, and if we have any, we use the first element in the hash map and find its original index. This gets populated into the answer variable, which will either be the index of that character's first appearance in the string, or -1.
In the case of our sample input, we know that the first character in the hash is b, so we use str_arr.indexOf("b") to find the character's index in the array and return that.
If no objects were left after the deduplication step, we'll return -1.
Through this post, we've dug into the basics of implementing a Hash map in O(n) time and using it to solve a simple algorithm.
These problems can get complex and quite difficult, so always remember to take breaks and be gentle with yourself on your journey through algorithms and data structures.
Let me know if you have any other fun solutions to this problem or other fun problems to solve!