Categories: Algorithmpython

String Compression in Python

Problem

Given a string in the form ‘AAAABBBBCCCCCDDEEEE’ compress it to become ‘A4B4C5D2E4’. For this problem, you can falsely “compress” strings of single or double letters. For instance, it is okay for ‘AAB’ to return ‘A2B1’ even though this technically takes more space.

The function should also be case sensitive, so that a string ‘AAAaaa’ returns ‘A3a3’.

Solution

Since Python strings are immutable, we’ll need to work off of a list of characters, and at the end convert that list back into a string with a join statement.

The solution below should yield us with a Time and Space complexity of O(n). Let’s take a look with careful attention to the explanatory comments:

def compress(s):
    """
    This solution compresses without checking. Known as the RunLength Compression algorithm.
    """
    
    # Begin Run as empty string
    r = ""
    l = len(s)
    
    # Check for length 0
    if l == 0:
        return ""
    
    # Check for length 1
    if l == 1:
        return s + "1"
    
    #Intialize Values
    last = s[0]
    cnt = 1
    i = 1
    
    while i < l:
        
        # Check to see if it is the same letter
        if s[i] == s[i - 1]: 
            # Add a count if same as previous
            cnt += 1
        else:
            # Otherwise store the previous data
            r = r + s[i - 1] + str(cnt)
            cnt = 1
            
        # Add to index count to terminate while loop
        i += 1
    
    # Put everything back into run
    r = r + s[i - 1] + str(cnt)
    
    return r
compress('AAAAABBBBCCCC')

‘A5B4C4’

Test Your Solution

"""
RUN THIS CELL TO TEST YOUR SOLUTION
"""
from nose.tools import assert_equal

class TestCompress(object):

    def test(self, sol):
        assert_equal(sol(''), '')
        assert_equal(sol('AABBCC'), 'A2B2C2')
        assert_equal(sol('AAABCCDDDDD'), 'A3B1C2D5')
        print('ALL TEST CASES PASSED')

# Run Tests
t = TestCompress()
t.test(compress)

ALL TEST CASES PASSED

Recommended: Understand Big-O Notation Complexity Of Algorithm

Follow Me ❤😊

If you like my post please follow me to read my latest post on programming and technology.

Instagram

Facebook

Recent Posts

Generate Parenthesis | Intuition + Code | Recursion Tree | Backtracking | Java

Problem Statement: Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example…

3 months ago

Square Root of Integer

Given an integer A. Compute and return the square root of A. If A is…

1 year ago

Build Array From Permutation

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where…

1 year ago

DSA: Heap

A heap is a specialized tree-based data structure that satisfies the heap property. It is…

2 years ago

DSA: Trie

What is a Trie in DSA? A trie, often known as a prefix tree, is…

2 years ago

Trees: Lowest Common Ancestor

What is the Lowest Common Ancestor? In a tree, the lowest common ancestor (LCA) of…

2 years ago