String Compression and Decompression

In competitive programming, dealing with strings efficiently is crucial to improve the performance of our solutions. One common technique used to optimize string manipulation is string compression. In this article, we will explore the concept of compressing and decompressing strings using the Java programming language.

String Compression

String compression involves transforming a given string into a shorter form by replacing repeated characters with a count of their occurrences. This compressed representation, also called a compressed string, occupies less space in memory and can be useful in scenarios where memory optimization is required.

Let's consider an example to understand the process of string compression. Given the string "AAABBBCCC", the compressed representation would be "A3B3C3". Here, each consecutive group of the same character is replaced by the character followed by the count of its occurrences.

To implement string compression in Java, we can use the following algorithm:

1. Initialize an empty StringBuilder to store the compressed string.
2. Traverse the input string character by character.
3. For each character, maintain a count of its consecutive occurrences.
4. If the next character is different from the current character or the end of the string is reached, append the current character and its count to the compressed string.
5. Continue this process until the entire input string is traversed.

Let's see the implementation of this algorithm in Java:

public String compressString(String input) {
    StringBuilder compressedString = new StringBuilder();
    int count = 1;

    for (int i = 0; i < input.length(); i++) {
        if (i + 1 < input.length() && input.charAt(i) == input.charAt(i + 1)) {
            count++;
        } else {
            compressedString.append(input.charAt(i));
            compressedString.append(count);
            count = 1;
        }
    }

    return compressedString.toString();
}

Using this implementation, we can compress any given string efficiently.

String Decompression

String decompression is the reverse process of string compression. It involves expanding a compressed string back into its original form. To achieve this, we need to decompress the compressed string by repeating characters according to their count.

Consider the compressed string "A3B3C3". The decompressed string would be "AAABBBCCC".

To implement string decompression in Java, we can use the following algorithm:

1. Initialize an empty StringBuilder to store the decompressed string.
2. Traverse the compressed string character by character.
3. For each character, check if it is a letter or a digit.
4. If it is a letter, simply append it to the decompressed string.
5. If it is a digit, convert it to an integer and repeat the last appended letter that many times.
6. Continue this process until the entire compressed string is traversed.

Let's see the implementation of this algorithm in Java:

public String decompressString(String compressedString) {
    StringBuilder decompressedString = new StringBuilder();

    for (int i = 0; i < compressedString.length(); i++) {
        if (Character.isLetter(compressedString.charAt(i))) {
            decompressedString.append(compressedString.charAt(i));
        } else {
            int count = Character.getNumericValue(compressedString.charAt(i));
            for (int j = 0; j < count; j++) {
                decompressedString.append(decompressedString.charAt(decompressedString.length() - 1));
            }
        }
    }

    return decompressedString.toString();
}

Using this implementation, we can decompress any given compressed string.

Conclusion

String compression and decompression are powerful techniques in the domain of competitive programming. By compressing strings, we can reduce memory usage and optimize performance. Similarly, by decompressing compressed strings, we can restore them to their original form when necessary. Understanding these techniques and implementing them efficiently can significantly enhance our ability to solve string-related problems efficiently using Java.