• Posts

Problem 3163 String Compression III

Problem Statement

Link - Problem 3163

Question

Given a string word, compress it using the following algorithm:

• Begin with an empty string comp. While word is not empty, use the following operation:
  • Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
  • Append the length of the prefix followed by c to comp.

Return the string comp.

Example 1:

Example 2:

Constraints:

• 1 <= word.length <= 2 * 105
• word consists only of lowercase English letters.

Solution

class Solution {
public:
    string compressedString(string word) {
        string comp = "";
        int size = word.size();
        comp.reserve(size*2);
        int ptr = 0;

        while (ptr < size) {
            int frq = 1;
            char ch = word[ptr];
            ptr++;

            while (ptr < size && word[ptr] == ch && frq < 9) {
                ptr++;
                frq++;
            }

            comp += (frq + '0');
            comp += ch;
        }

        return comp;
    }
};

Complexity Analysis

| Algorithm           | Time Complexity | Space Complexity |
| ------------------- | --------------- | ---------------- |
| Run-length encoding | O(n)            | O(n)             |

Explanation

Intial Thoughts

To solve this problem, we should start by understanding the compression algorithm. It involves removing a prefix of the input string that consists of the same character repeated at most 9 times. We then append the length of this prefix and the character itself to the result string. This process repeats until the input string is empty. Key points to consider are:

1. Identify the repeated character prefixes in the string.
2. Determine the length of each prefix, ensuring it doesn’t exceed 9.
3. Append the prefix length and character to the result string.
4. Continue the process until the entire string is processed.
5. Handle edge cases, such as an empty input string or single-character strings.

Intuitive Analysis

Intuitively, we can approach this problem by thinking of it as a process of scanning the input string from left to right, identifying blocks of consecutive identical characters, and representing each block with its length and the character. Important insights include:

1. Use a pointer to track the current position in the string.
2. Compare characters to identify blocks of the same character.
3. Keep a count of the length of each block.
4. When a block ends, append its length and character to the result string.
5. Repeat this process until the end of the string is reached, resulting in the compressed string.

1. Intuition

• The problem requires compressing a given string by replacing repeated characters with their count and character.
• To solve this, we can iterate through the string and keep track of the current character and its frequency.
• We should stop counting the frequency when we encounter a different character or when the frequency reaches 9.
• The key insight is to use a while loop to iterate through the string and another nested while loop to count the frequency of each character.
• This approach ensures that we process each character in the string exactly once, resulting in a time complexity of O(n).
• The space complexity is also O(n) because in the worst case, we might end up with a compressed string of the same length as the original string.
• The algorithmic choice of using a while loop and a reserve function for the result string is efficient and easy to implement.

2. Implementation

• We start by initializing an empty string comp to store the compressed result and a pointer ptr to keep track of the current position in the string.
• The line comp.reserve(size*2) is used to preallocate memory for the result string to avoid reallocations during the compression process.
• The outer while loop iterates through the string, and the inner while loop counts the frequency of each character using the condition word[ptr] == ch && frq < 9.
• The frequency is converted to a character using frq + '0' and appended to the result string comp along with the character ch.
• The use of ptr++ ensures that we move to the next character in the string after processing the current one.
• Finally, the compressed string comp is returned as the result.
• The tradeoff here is between the time complexity of the algorithm and the space complexity of storing the result string.

Complexity Analysis

Time Complexity:

• The algorithm iterates over the string word once, using a while loop that increments ptr until it reaches the end of the string, resulting in a linear time complexity of O(n).
• The dominant operation is the comparison word[ptr] == ch, which is performed within the nested while loop, but since this loop also increments ptr and only runs for a portion of the string, it does not increase the overall time complexity beyond O(n).
• Mathematically, if we consider the string length as n, the number of operations (comparisons and concatenations) grows linearly with n, hence the time complexity is O(n), which encompasses the worst, average, and best cases.

Space Complexity:

• The algorithm creates a new string comp to store the compressed version of word, with comp.reserve(size*2) ensuring enough space for the compressed string, which in the worst case could be larger than the original string if no characters are repeated.
• The data structure impact comes from the strings comp and word, where the size of comp can grow up to twice the size of word in the worst-case scenario (when no compression is achieved), thus affecting the space complexity.
• The space complexity is O(n) because the memory usage grows linearly with the size of the input string word, considering both the original string and the newly created comp string, which can be at most twice the size of word.

Footnote

This question is rated as Medium difficulty.

Hints

Each time, just cut the same character in prefix up to at max 9 times. It’s always better to cut a bigger prefix.

Similar Questions: