String Compression LeetCode Solution

Table of Contents

Problem Statement

String Compression LeetCode Solution – 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

Test Case 1:

Input:

chars = [“a”, “a”, “b”, “b”, “c”, “c”, “c”]

Output:

Test Case 2:

Input:

chars = [“a”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”, “b”]

Output:

Explanation

i) The groups are “aa”, “bb”, “ccc”. It compresses to “a2b2c3”. The array basically is [“a”, “2”, “b”, “2”, “c”, “3”].

ii) The groups are “a”, “bbbbbbbbbbbb”. It compresses to “ab12”.

Approach:

So here I am going to explain algo. Firstly we are going to take a example “aabbccc“. so in this example firstly we will append a into a string or stringbuilder then we will make its count 1 as one of one is there now we will move to for loop . In for loop we are using two pointers one is current and another is prev prev stores previous character and current stores current character now as:-

we are iterating from 1 as the 1st charcter is already in string buildernow iterating

1->prev = a , curr = a so count will be 2 . s = a

2->prev = a , curr = b so we will not increase rather will go to else part where we will check if count>1 then we will append it and will also append the char . and reset the count to 1 . a2->a2b

3->prev=b, curr =b count = 2 s=a2b

4->prev= b , curr = c count = 2 so will go in else part as prev!=curr count > 2 so s= a2b2-> a2b2c count =1

5->prev = c ,curr = c count =2 s =a2b2c

6->prev = c , curr = c count =3 s =a2b2c

Now here iteration will stop and our count is still remaining so at last outside the loop we will add the count if >1so string will be a2b2c3.

So the string is compressed now we will copy it to char array. and return its length.

Code for String Compression

Java Program

class Solution {
    public int compress(char[] chars) {
        StringBuilder sb = new StringBuilder();
        int  n = chars.length;
        int count = 1;
        sb.append(chars[0]);
        for(int i=1;i<n;i++)
        {
           char curr = chars[i];
           char prev = chars[i-1];
           if(prev==curr)
           {
               count++;
           }
           if(prev!=curr)
           {   if(count>1)
               sb.append(count);
               sb.append(curr);
               count = 1;
           }
        }
        if(count>1)
        {
            sb.append(count);
        }
     
        for(int i=0;i<sb.length();i++)
        {
            chars[i]=sb.charAt(i);
        }
        return sb.length();
    }
}

C++ Program

class Solution {
public:
    int compress(vector<char>& chars) {
        int nw_idx = 0;     // Next write index
        int nr_idx = 1;     // Next read index
        int cnt = 1;        // Running counter
        char prev_char = chars[0];  // Running previous character
        chars.push_back('\0');      // To make the code shorter (no special handling of last char)
        
        // Code below is more or less self explanatory
        while(nr_idx != chars.size()) {
            if(chars[nr_idx] != prev_char) {
                chars[nw_idx++] = prev_char;
                if(cnt > 1) {
                    string cnt_str = to_string(cnt);
                    for(char c : cnt_str) chars[nw_idx++] = c;
                    cnt = 1;
                }
            } else {
                cnt++;
            }
            prev_char = chars[nr_idx++];
        }
        return nw_idx;
    }
};

Complexity Analysis for String Compression LeetCode Solution

Time Complexity will be $O (n),$ $where n is size of array as we are just iterating over the array only once.$

Space Complexity will be $O (n),$ $where n is size of array as we are storing the value in another string.$

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique