LeetCode Challenge #443. String Compression

Question 9 of 75 - LeetCode Weekly Challenge

Day 48 of 100 Days LeetCode Challenge

LeetCode Challenge #443. String Compression

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.

C++ Video Solution

Java Video Solution

C++ Solution

				
					class Solution {
public:
    int compress(vector<char>& nums) {
        int n=nums.size();
        string s="";
        nums.push_back('*'); // for not getting the error as we will check for nums[i+1] in the loop
        int freq=1;
        for(int i=0;i<n;i++){
            char c=nums[i];
            if(nums[i+1]==c){ //checking if current character is equal to the next character
                freq++;
            }
            else{
                s+=c;
                if(freq>1){ //if freq=1 then no need to append the frequency
                    s+=to_string(freq);
                    freq=1;
                }
            }
        }
        for(int i=0;i<s.length();i++){
            nums[i]=s[i]; // for copying back
        }
        return s.length();
    }
};

Java Solution

				
					class Solution {
    public int compress(char[] chars) {
        int count = 1 ;
        StringBuilder sb = new StringBuilder("");

        sb.append(chars[0]);

        for(int i = 1 ;i<chars.length;i++){

            if(chars[i-1]!=chars[i]){
                if(count>1){
                    sb.append(count+"");
                }
                sb.append(chars[i]);
                count = 1;

            }else{
                count++;
            }
        }

        if(count>1){
            sb.append(count+"");
        }

        for(int i=0;i<sb.length();i++){
            char ch = sb.charAt(i);
            chars[i]=ch;
        }

        return sb.length();


    }
}

Code Explanation

In this program the goal is to make a list of let’s say,characters , like letters or numbers and make the list shorter by counting how many times the same character appears in a row writing that number next to the character.

Let’s see the step-by-step approach of the code:

Here ‘nums’ represents a sequence of characters.

And let us first calculate the size n= nums.size()

Now to prevent errors in the loop we will add a special character let’s say (“ * “) at the end of the vector.

For counting the consecutive occurrences of character we need to initialise a variable ‘freq’ to 1 ( freq=1 ) . This will help us in counting the number of characters .

Now , let’s start the iteration on array, by using simple “for” loop . Inside the loop ,it compares the current character ‘c’ with the next character . Because there are two possible conditions here , either the next adjacent element is same or it’s different .

Now , if they are same increment the count (‘freq’)to keep track of all consecutive occurrences.

And if, the next character is different we will append the character in the string ‘c’( as said in the question) and if the

Count (‘freq’) is greater than 1 we have to append the ‘freq’ as well.

After the loop , We have used here two string function to store the compressed string ‘s’ which contains the the compressed version of the original string.

The code then copies the compressed string back into the original vector ‘nums’

Finally , the function returns the length of the compressed string.

In simpler terms ,it’s like making a list of how many times each letter appears in a row, and then writing a shorter version of the list with that information.

Question 9 of 75 - LeetCode Weekly Challenge

Day 48 of 100 Days LeetCode Challenge