String Compression. Facebook interview question. 
Tags: javascript, tutorial, career, webdev
Published: 2020-04-25 15:26:39

Question: Design a system that will compress the string and then decode it. The input will consist only of alphabet characters. 

Eg: if the string is: aaabbcccccd 
1> it's compressed form ie encoded form will be a3b3c5d1. 
2> then we have to take the compressed string and decode it. 

<h6>note: this is a string manipulation question and is meant to test your string manipulation skills, don't confuse it with compression algorithms since there are much better compression algorithms.</h6>

Imagine a system similar to this : 
<img src = "https://media.giphy.com/media/3o7qDXyFRvBmn411Qc/giphy.gif" />
String "Richard is great but you know" is compressed to RIGBY which both the client and server know what that string represents. 

One can use it for their projects: 
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ftxwpjxr3os2zrfgeu8l.png)


<h2>Enconding the string / compression</h2>

The algorithm is pretty straight forward, keep a pointer and move ahead. Count the number of times a character repeats and append the character and it's count to a result string.

```javascript 
var encode = function(string){
  let chars = string.split("");
  let res = "";
  for(let i=0;i<chars.length;i++){
      let count = 1;              //default count = 1 since at least 1 character
      let char = chars[i];        //the character at that pointer
      while(i<chars.length-1 && chars[i] == chars[i+1]){
        count++;                  // increment the count
        i++;                      // increment the pointer
      }
      res += char + count;        // append to resultant string.
  }
  return res;
}
```


<h2>Decoding the string</h2>

Decoding the string is also similar, we keep a pointer, get the character, get its count, generate character and append it to the resultant string. 

```javascript
var decode = function(string){
  let res = "";
  for(let i=0;i<string.length;){
    let char = string[i];
    let count = 0;
    i++;
    while(i<string.length && parseInt(string[i])>=0 && parseInt(string[i])<=9){
      count = parseInt(count * 10) + parseInt(string[i]);
      i++;
    }
    while(count>0){
      res+= char;
      count--;
    }
  }
  return res;
} 
```

Putting them together:  
```javascript
var encode = function(string){
  let chars = string.split("");
  let res = "";
  for(let i=0;i<chars.length;i++){
      let count = 1;
      let char = chars[i];
      while(i<chars.length-1 && chars[i] == chars[i+1]){
        count++;
        i++;
      }
      res += char + count;
  }
  return res;
}

var decode = function(string){
  let res = "";
  for(let i=0;i<string.length;){
    let char = string[i];
    let count = 0;
    i++;
    while(i<string.length && parseInt(string[i])>=1 && parseInt(string[i])<=9){
      count = parseInt(count * 10) + parseInt(string[i]);
      i++;
    }
    while(count>0){
      res+= char;
      count--;
    }
  }
  return res;
} 

let compress = encode("aaabbbccccccccccccd");
console.log(compress);
let res = decode(compress);
console.log(res);

```

That's it, now you know how to solve a Facebook interview question and a bit of introduction towards compression.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/stringCompression.js

Special thanks to the community for pointing out bugs and edge cases !! 🥰