Cracking the Code Challenge: Run Length Encoding
Another week, another algorithm…
Hi friends! I had a CoderByte assessment for another job application this week that threw me a little bit for a loop: run length encoding. This is a concept I had never heard of so I figured it would be helpful for others to break it down, along with the problem and my solution.
***Full disclosure and reminder that this is by no means the PERFECT solution to this algorithm and I’m sure there are more “correct” and more efficient answers on the internet; this is just the way I was able to logically solve it in my brain with time constraints!***
THE PROBLEM
Given an input string, write a function that returns a compressed version of the string using the Run-length encoding algorithm. This algorithm works by taking the occurrence of each repeating character and outputting that number along with a single character of the repeating sequence. For example: “wwwggopp” would return 3w2g1o2p. The string will not contain any numbers, punctuation, or symbols.
BREAKING DOWN RUN-LENGTH ENCODING
The first thing I thought when I read this problem was “What the hell is run-length encoding?” I had no flipping clue, and had never heard of this concept in my life. So, what better time then now to learn?
I like Wikipedia’s definition:
Run-length encoding (RLE) is a form of lossless data compression in which runs of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run.On first glance this seems like a silly and useless concept, but in situations where there are very very large runs of characters, I see where this can make things more efficient.
MY SOLUTION
https://replit.com/@thequeenbeebs/RunLengthEncoding
THE METHOD TO MY MADNESS
Building Out Initial Variables
let count = 1
let finalString = string[0]The first thing I thought of when I saw this problem was that I was going to need to loop through each character in the string and create some sort of counter to determine the number of each character. I built a variable called “count” that would tell us the number of each character, and increment as we looped through the string.
I also wanted to create a string that would contain all of the final information that we would eventually return. The reason I didn’t begin by creating it as an empty string was that I knew that we would need something to compare to when looping through the input string, so I added the first character from the string. So, right now, using the example above, finalString would simply be “w”, and the count would be 1 to represent the 1 character we have already looped through.
Looping through Each Character in the String
for (let i = 1; i < string.length; i++) {
...
}For this loop, I decided to use this style of iteration instead of a for/in situation, because I knew that I actually wanted to just start with the second character in the string, and compare it to the first character already in our finalString variable.
The Conditional: Part 1
if (string[i] === finalString[finalString.length - 1]) { count += 1}
So, what this conditional does is checks and sees if the current character in the loop is the same as the character before it, which we have added to our finalString and is currently the last character.
If we are still using our example from above, string[1] would be “w”, and finalString[0] would also be “w”. So, this conditional returns true and we add one more to the count.
The Conditional: Part 2
else { finalString = finalString.slice(0, finalString.length - 1) + count + finalString.slice(finalString.length - 1) + string[i] count = 1}
This is the part that gets a little tricky. What happens when we move on from one character to the next, when we’ve hit the 4th character in the string, “g”?
I’m sure there is a more elegant way to come up with a solution but the one I found is to slice up finalString like so:
all the characters in the finalString except the last one+the counter we have been adding to + the character we have been comparing the other characters with+the new character that we have come across, that we will now be using to compare against other characters
It’s a little confusing, but this will give you the exact format you need for this problem. In this situation, if we put a console.log() inside this else conditional, the first one would come up as “3wg”. There is only one character in finalString at the moment, so there is nothing before the count, which is 3. After that we have the “w” that we have been referencing the whole time, and then the “g” that we will be referencing after that.
The last thing you need to do is reset the count variable to 1, since we are starting over and counting the instances of a new character.
Tacking on the Final Count
finalString = finalString.slice(0, finalString.length - 1) + count + finalString.slice(finalString.length - 1)The only thing that this loop does not accomplish is that there will be still one more count that needs to be tacked onto the finalString after we have finished iterating. Like in the else conditional above, we are putting the count inside slices of finalString so it’s in the exact position that we need. The only thing that is different is that we are not tacking another character on the end of finalString, because we’ve looped through them all and there’s nothing else to compare!
Put this code outside of both the conditionals and the looping, so that it is only performed once right before we return the finalString.
Return finalString
return finalStringThat’s it! You’re done!
I’m really interested in seeing other people’s solutions to this problem, so feel free to comment and let you know how you’d tackle run-length encoding. Happy coding!
