String Compression III

Leetcode Problem:

• String Compression III

Summary

• Given a string word, compress it using the algorithm where a maximum length prefix of a single character c repeating at most 9 times is removed, and the length of the prefix followed by c is appended to the compressed string.

Approach

• The approach used is to iterate through the input string and whenever a different character is encountered, the length of the previous character's prefix is appended to the compressed string, followed by the character
• This process continues until the end of the string.

Complexity

• O(n), where n is the length of the input string, because each character in the string is visited once.

Explanation

• The code uses a dynamic programming approach to solve the problem
• It first initializes a counter cnt to keep track of the length of the current character's prefix
• It then iterates through the input string, and whenever a different character is encountered, it calculates the length of the previous character's prefix (a and b) and appends it to the compressed string
• The counter cnt is then reset to 0 and the process continues until the end of the string.

Solution Code:

class Solution {
public:
    int str_cnt[256];
    string compressedString(string word) {
        int cnt = 0;
        char beforeChar = 'a'-1;
        string res = "";
        for(char c : word) {
            if(c != beforeChar){
                int a = cnt / 9;
                for(int i = 0 ; i < a; i++){
                    res += "9" + string(1, beforeChar);
                }
                int b = cnt % 9;
                if (b > 0){
                    res += to_string(b) + string(1, beforeChar);
                }
                cnt = 0;
            }
            cnt++;
            beforeChar = c;
        }
        int a = cnt / 9;
        for(int i = 0 ; i < a; i++){
            res += "9" + string(1, beforeChar);
        }
        int b = cnt % 9;
        if (b > 0){
            res += to_string(b) + string(1, beforeChar);
        }
        
        return res;
    }
};