Day 4 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#443.String Compression(Medium/JavaScript)
Tags: javascript, beginners, algorithms, leetcode
Published: 2022-02-14 04:33:23

**Intro:** I am a former accountant turned software engineer graduated from coding bootcamp in January 2022. Algorithms and Data Structure is an unavoidable part of interviews for most of the tech companies now. And one of my friends told me that you need to solve a medium leetcode problem under 60 seconds in order to get into the top tech companies.So I thought I'd start learning how to do it while job searching.

Since I have no clue on how to solve any of the problems (even the easy ones), I thought there is no point for me to waste hours and can't get it figured out. **Here is my approach:**
- Pick a leetcode problem randomly or Online Assessment from targeted companies.
- Study 1-2 solutions from Youtube or LeetCode discussion section. One brute force solution, another one more optimal.
- Write a blog post with detailed explanation and do a verbal walk through to help understand the solutions better.
- Code out the solution in LeetCode without looking at the solutions
- **Combat the forgetting curve:** Re-do the question for the next three days. And come back regularly to revisit the problem.

******************************************

## Problem#443. String Compression
`Difficulty: Medium` `Language: JavaScript` 

<!-- `Company: IBM Backend Developer OA` -->

Given an array of characters `chars`, compress it using the following algorithm:

Begin with an empty string `s`. For each group of **consecutive repeating characters** in `chars`:

If the group's length is `1`, append the character to `s`.
Otherwise, append the character followed by the group's length.
The compressed string `s` **should not be returned separately**, but instead, be stored **in the input character array** `chars`. Note that group lengths that are 10 or longer will be split into multiple characters in `chars`.

After you are done **modifying the input array**, return the _new length of the array_.

You must write an algorithm that uses only constant extra space.

Example 1:
```
Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array
should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses
to "a2b2c3".
```
Example 2:
```
Input: chars = ["a"]
Output: Return 1, and the first character of the input array
should be: ["a"]
Explanation: The only group is "a", which remains uncompressed
since it's a single character.
```
Example 3:
```
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array
should be: ["a","b","1","2"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This
compresses to "ab12".
```
Constraints:
- `1 <= chars.length <= 2000`
- `chars[i]` is a lowercase English letter, uppercase English
letter, digit, or symbol.

******************************************

##Solution:
```
var compress = function(chars) {
    let count = 1;

    for (let i = 1; i <= chars.length; i++) {
        if (chars[i] == chars[i - 1]) {

/*start iterating from second character and compare it with the
previous character*/

            count++;

/*if same character is found, increase count by 1 (note 1)*/

        } else {
            if (count > 1) {
                let countArr = count.toString().split(''); 

/*convert count from integer to string (note 2). And "split()"
(note 3) is to make sure that when count is a two digit integer,
for example, 12, it will be split into multiple characters: "1"
and "2" then stored in the array (part of the requirement).*/

                let deletedElement = chars.splice(i - count + 1,
                                  count - 1, ...countArr); 

/*Delete duplicated elements and replace them with character count
(note 4)*/

                i = i - deletedElement.length + countArr.length;

/*reset the index to the start of new character. In test case:
["a","a","a","b","b"], the index for the three "a" are 0, 1, 2 and
index for the first "b" is 3. Once we compress all the "a" and
modify the array with the count, we will get a new array
["a","2","b","b"]. And in this new array, the index of the first
"b" becomes 2. This solution uses "i - deletedElement.length +
countArr.length" to reset i to the new character.*/

            }
            count = 1;

/*reset the count back to 1, so that counting starts again with
new character*/

        }
    }

    return chars.length;

};
```
**Solution Submission detail as of 2/13/2022** 
(Data below could vary since there are new submissions daily)
- Runtime: 73ms
- Memory Usage: 44MB 
- Time complexity:O(n)
- Space complexity:O(1)

******************************************

**References:**
[LeetCode Problem Link](https://leetcode.com/problems/merge-intervals/)
[LeetCode Discussion: galberto807](https://leetcode.com/problems/string-compression/discuss/1125644/Js-Javascript-One-Loop-Easy-Understand-Remove-Elems-and-Add-Nums-in-a-Single-Splice-Function)
[Note 1: Increment(++)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Increment)
[Note 2: toString()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/toString)
[Note 3: split('')](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/split)
[Note 4: splice()](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/splice)
[Blog Cover Image Credit](https://www.istockphoto.com/portfolio/monsitj?mediatype=photography)