Nuxtstop

For all things nuxt.js

Day 4 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#443.String Compression(Medium/JavaScript)

#javascript #beginners #algorithms #leetcode
Day 4 of Studying LeetCode Solution until I Can Solve One on My Own: Problem#443.String Compression(Medium/JavaScript)
8 0

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

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".
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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".
Enter fullscreen mode Exit fullscreen mode

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;

};
Enter fullscreen mode Exit fullscreen mode

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
LeetCode Discussion: galberto807
Note 1: Increment(++)
Note 2: toString()
Note 3: split('')
Note 4: splice()
Blog Cover Image Credit

Add comment