String Compression: "String Compression III" Problem | Leetcode 3163 | Medium | String

String manipulation is a common task in programming, especially when it comes to optimizing data storage or transmission. One fascinating challenge is the "String Compression III" problem from LeetCode, which requires you to compress a string according to specific rules. In this post, we’ll explore the problem statement, discuss a practical solution, and delve into the intricacies of the algorithm. Whether you’re preparing for coding interviews or simply want to enhance your problem-solving skills, this guide will provide valuable insights.

Problem Statement

You are given a string called word, and your task is to compress it using a specific algorithm. The rules for compression are as follows:

1. Begin with an empty string comp.
2. While word is not empty, remove a maximum length prefix made of a single character c, which can repeat at most 9 times.
3. Append the length of the prefix followed by the character c to comp.
4. Continue this process until all characters in word are processed.

Examples

Let’s look at a couple of examples to clarify the requirements:

• Example 1:

  • Input: word = "abcde"
  • Output: "1a1b1c1d1e"
  • Explanation: Each character appears only once, so the output reflects this straightforwardly.

• Example 2:

  • Input: word = "aaaaaaaaaaaaaabb"
  • Output: "9a5a2b"
  • Explanation: Here, the string has a long sequence of 'a's, which can be compressed to '9a' for the first nine, followed by '5a' for the next five, and '2b' for the last two 'b's.

Constraints

• The length of word is between 1 and 200,000 characters.
• The string consists only of lowercase English letters.

Designing the Solution

To solve the problem effectively, we can adopt an iterative approach. We will traverse the string, counting occurrences of each character until we hit a different character or reach the limit of 9 repetitions. Let’s break down the steps involved in the solution.

Step-by-Step Approach

1. Initialize Variables: Start with the first character and initialize a count for its occurrences.
2. Iterate Through the String: For each character:
   • If it matches the current character, increase the count (up to 9).
   • If it changes, append the count and the character to the result string and reset the count.
3. Final Append: After the loop, don’t forget to append the count and character for the last group.
4. Return Result: Finally, return the compressed string.

Implementation

Here’s a C++ implementation based on the approach we just discussed:

class Solution {

public:

    string compressedString(string word)

    {

        char ch = word[0]; // Start with the first character

        int count = 1; // Initialize count for the first character

        string ans = ""; // Result string for compressed output

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

        {

            if(word[i] == ch) // Check if current character matches the previous

            {

                if(count < 9)

                    count++; // Increase count, not exceeding 9

                else

                {

                    ans += char(count + '0'); // Append count

                    ans += ch; // Append character

                    count = 1; // Reset count for the next character

                }

            }

            else // When character changes

            {

                ans += char(count + '0'); // Append previous count

                ans += ch; // Append previous character

                ch = word[i]; // Update character to the new one

                count = 1; // Reset count for the new character

            }

        }

        // Append the last counted character

        ans += char(count + '0');

        ans += ch;

        return ans; // Return the compressed string

    }

};

Explanation of the Code

• Variable Initialization: We begin with the first character and a count set to 1. The result string ans is initialized as empty.
• Main Loop: We loop through the string starting from the second character, checking for matches with the current character.
• Count Handling: We ensure the count does not exceed 9, appending to the result string when it changes.
• Finalizing the Result: After exiting the loop, we must remember to append the last counted character.

Complexity Analysis

• Time Complexity: The algorithm runs in O(n), where n is the length of the string. Each character is processed exactly once.
• Space Complexity: The space complexity is O(n) in the worst case due to the storage of the output string, but this is efficient given the nature of the problem.

The "String Compression III" problem is an excellent exercise in string manipulation and algorithmic thinking. By following a systematic approach, we can efficiently compress a string while adhering to the specified rules. This problem not only sharpens our coding skills but also enhances our understanding of data structures and algorithms.

Whether you’re tackling similar problems or preparing for technical interviews, mastering string manipulation techniques like these will serve you well in your programming journey.