String Compression

Hi Everyone! It’s been a while~

As of right now, I am a Senior Technical Support Engineer at my company! It’s been great work, I get to solve everyday real world problems. While as a Support Engineer, we don’t code a lot, but we still deal with our code platform and continue to test and implement it’s integration.

With that said, it’s important to continue to practice your algorithms and to code! Without further ado, the steps below are how to solve the String Compression problem:

Question

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string “aabcccccaaa” would become “a2b1c5a2”. If the compressed string is longer than the original, return the original string. (cracking the coding interview)

The same problem, different flavor can be found on LeetCode: https://leetcode.com/problems/string-compression/

Answer

First, I created my variables, defined my function and split the string. I created the hash to keep track of which letters I will encounter as we loop through the string:

const stringCompression = (string) => {
let str = string.split("");
let count = 0;
let hash = {};
let result = "";
}

Next, I created my for-loop to loop through the newly split string:

for (let i = 0; i < str.length; i++) {
}

The hash will hold onto which letters we have encountered. This is important! The logic is as follows,

• If the current iteration does NOT exist in the hash, store it in the hash = to itself.
• Then, if the current iteration and the next are not the same, increment the count variable, add the current letter to the result variable + the count, and set the count = 0.
• Else, increment the count

for (let i = 0; i < str.length; i++) {
if (!hash[str[i]]) {
hash[str[i]] = str[i];
//first bullet point ^
if (str[i] !== str[i + 1]) {
count++;
result += str[i] + count;
count = 0;
//second bullet point ^
} else {
count++;
//third bullet point ^
}

• If the current iteration DOES exist in the hash and…
• If the current iteration and the next are not the same, increment the count variable, add the current letter to the result variable + the count, and set the count = 0.
• Else, increment the count

else if (hash[str[i]]) {
if (str[i] !== str[i + 1]) {
count++;
result += str[i] + count;
count = 0;
//second bullet point ^
} else {
count++;
//third bullet point ^
}
}

Notice the repetition? For example, [“a”, “a”, “b”, “c”], at the second “a”, our counter has incremented to 2, and to eliminate the possibility of concatenating, a letter multiple times, we’re concatenating the last “a” (refer to bullet point 2 and bullet point 4). If they are the same, “a” and “a”, the count will continue to increase.

Lastly, we need to compare the string lengths, aka the edge case scenario listed earlier,

If the compressed string is longer than the original, return the original string.

if (result.length > str.length) {
return str;
} else {
return result;
}

Here is the code all together!

const stringCompression = (string) => {
let str = string.split("");
let count = 0;
let hash = {};
let result = "";
for (let i = 0; i < str.length; i++) {
if (!hash[str[i]]) {
hash[str[i]] = str[i];
if (str[i] !== str[i + 1]) {
count++;
result += str[i] + count;
count = 0;
} else {
count++;
}
} else if (hash[str[i]]) {
if (str[i] !== str[i + 1]) {
count++;
result += str[i] + count;
count = 0;
} else {
count++;
}
}
}
if (result.length > str.length) {
return str;
} else {
return result;
}
};
stringCompression("aabcccccaaa");
// returns "a2b1c5a3"

Happy Hacking!

-Crystal