Interview Prep #5: String Compression

#career #beginners #cpp #computerscience

Problem

We are given a string which we are supposed to compress by using the count of the repeated characters.

Example:

input: aabbbcccccaa
output: a2b3c5a2

If the compressed string is not smaller than the original string we shall return the original string.

Solution

The solution to this problem involves trivial string manipulation. First we create a copy string which is twice the size of the given string. This is the maximum size the compressed string can get (if all characters are unique). We will edit this copy string to construct the compressed string. We iterate through the original string and find out the number of character count and edit the the second string accordingly. For doing this will use two pointers. First to keep track of the character we are on the second will count the number of occurrences of the same character. In the end will compare the two strings and then return the smaller one.

string compressed_string(string& s) {
  string copy = s + s;
  // i is the first pointer, j is the second pointer
  // c keeps track of where we are on in the copy string
  int c = 0, i = 0;
  while(i < s.length()) {
    int j = 1;
    while(i + j < s.length() && s[i] == s[i + j]) {
      ++j;
    }
    copy[c] = s[i];
    copy[c + 1] = j + '0';
    c += 2;
    i += j;
  }
  // erase the remaining copy string
  copy.erase(c);
  if(copy.length() < s.length()) {
    return copy;
  }
  return s;
}

References: Cracking the Coding Interview - Gayle Laakmann McDowell
Hey! I realized that many of you guys don't use C++. If you are comfortable with some other language, feel free to submit the solution to this problem in your favorite programming language in the comments below.
Have a wonderful day 😄