String Compression and Decompression

In competitive programming, one often encounters problems involving efficient manipulation of strings. One such problem is string compression and decompression, where we are required to compress a given string or decompress a compressed string.

String Compression

String compression is the process of representing a given string in a compressed format. This compression is typically achieved by replacing multiple consecutive occurrences of the same character with a single occurrence of that character followed by the count of consecutive occurrences.

Let's consider an example to better understand string compression. Given the string "aaabbbcc", the compressed form would be "a3b3c2". Notice how consecutive occurrences of characters are replaced by the character itself followed by the count.

To compress a string, we can make use of two pointers. The first pointer moves sequentially through the string and checks if the next character is the same. If the next character is the same, we increment a count variable. Once we encounter a different character, we append the current character with its count to the result string and reset the count variable. This process continues until we traverse the entire string.

Here's a C++ implementation for string compression:

string compressString(string str) {
    string compressed;
    int count = 1;
    
    for (int i = 0; i < str.size(); i++) {
        char current = str[i];
        
        // Check if the next character is the same
        while (i + 1 < str.size() && str[i + 1] == current) {
            count++;
            i++;
        }
        
        // Append the character with its count
        compressed += current + to_string(count);
        
        // Reset the count
        count = 1;
    }
    
    return compressed;
}

String Decompression

String decompression is the process of reversing the string compression operation. Given a compressed string, we need to decompress it back to its original form.

To decompress a string, we can make use of a similar approach as string compression. We iterate through the compressed string and check if the current character is followed by a digit. If it is, we extract the count and append the character the required number of times to the result string. This process is repeated until we traverse the entire compressed string.

Let's consider an example for a better understanding. Given the compressed string "a3b3c2", the decompressed form would be "aaabbbcc". Here, each character is repeated the number of times mentioned after it in the compressed string.

Let's take a look at the C++ implementation for string decompression:

string decompressString(string compressed) {
    string decompressed;
    
    for (int i = 0; i < compressed.size(); i++) {
        char current = compressed[i];
        
        // Check if the current character is followed by a digit
        if (isdigit(compressed[i + 1])) {
            int count = compressed[i + 1] - '0'; // Extract the count
            
            // Append the character the required number of times
            while (count > 0) {
                decompressed += current;
                count--;
            }
            
            i++; // Skip the count digit
        } else {
            decompressed += current;
        }
    }
    
    return decompressed;
}

Conclusion

String compression and decompression are essential techniques in competitive programming for efficient string manipulation. By understanding the concepts and implementing the provided algorithms, we can efficiently compress and decompress strings, solving related problems with ease.