Lecture 80 :-  String Compression

String compression is the process of representing a string by replacing consecutive repeated characters with a single character followed by the count of repetitions. This can be useful in various scenarios, such as data compression or optimizing storage.

For example, the string "aaabbbccc" can be compressed to "a3b3c3".

To implement string compression, you can iterate through the characters of the input string and maintain a count of consecutive occurrences of each character. If a character changes or the end of the string is reached, you can append the character and its count to a new compressed string.

Here's a Python function to perform string compression:

pythonCopy code

def compress_string(s):    if not s:        return ""    compressed_string = ""    count = 1    prev_char = s[0]    for i in range(1, len(s)):        if s[i] == prev_char:            count += 1        else:            compressed_string += prev_char + str(count)            count = 1            prev_char = s[i]    # Add the last character and its count    compressed_string += prev_char + str(count)    # Check if the compressed string is shorter than the original string    return compressed_string if len(compressed_string) < len(s) else s # Example usage: input_str = "aaabbbccc" output_str = compress_string(input_str) print(output_str)

Output:

Copy code

a3b3c3

In this example, the function compress_string takes the input string s, iterates through its characters, and constructs the compressed string. The compressed string is only returned if it is shorter than the original string. If the compressed string is longer or of the same length as the original string, the function returns the original string.

Keep in mind that string compression may not always reduce the string length. It is most effective when there are consecutive repeated characters in the input string. For certain strings, it may even result in a longer output.