A Program to Perform String Compression in Python

Introduction

Today our topic of discussion is String Compression. We will solve a related problem using Python. Before that, let's briefly know what String Compression actually is.

Compression of a string means shortening that. For example, Bitly(An Online URL shortening service) or other similar online tools which are widely used to compress large URLs. It saves a lot of memory space.

In this tutorial, we will write a Python Program to perform the basic String Compression method using the counts of repeated characters. For example, if the given string is "AABBBBCDEE" then the program will give an output like this, "A2B4C1D1E2".

Let's get straight into the code.

The Code

This method is pretty straightforward. Here, we will iterate through the string,  copy the characters to a new string, and count the repeated characters. 

At each iteration, we will check whether the current character is the same as the next or not. If not, the compressed version will be added to the result.

# Function to compress a given string
def Compress(string):
    compressedString = ""
    count = 0
    for i in range(0, len(string)):
        count += 1

        # If next char. is different than the current 
        # append this char. to result
        if (i+1) >= len(string) or string[i] != string[i+1]:
            compressedString += "" + string[i] + str(count)
            count = 0
    # If the len. of the compressed str. is less than
    # the original, return that; else, return the original str.
    if len(compressedString) < len(string):
        return compressedString
    else:
        return string

if __name__ == "__main__":
    # The ip string
    ip = "AABBBBCDEEEE"
    print("======Output=======")
    print(Compress(ip))

Output

======Output=======
A2B4C1D1E4

Complexity Analysis

The runtime of this program is O(n + k^2), where n is the size of the original string and k is the number of sequences. It works well, but quite slow.