# String Compression

Implement a method to perform string compression using the counts of repeated characters. If the “compressed” string would not become smaller than the original, return the original string.

Assume that the string has only upper and lower case letters (a-z)

### Example

1
2
Input:  aabcccccaaa
Output: a2b1c5a3


### Solution

Complexity: $T = O(n), S = O(n)$ (to store the output)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def compress(st):
result = bytearray() # Bytearray is mutable
if len(st) == 0:
return result
count = 1
current = st[0]
result.append(current)
for idx in xrange(1, len(st)):
if st[idx] == current:
count += 1
else:
result.append(str(count))
count = 1
current = st[idx]
result.append(current)
result.append(str(count))
if len(result) > len(st):
return st
return result

st = 'aabcccccaaa'
print 'Result:', compress(st)

Result: a2b1c5a3


### Zafar

I am a 5th year PhD student at Boston University, working towards my degree in Computer Engineering. While my work focuses on digital design,error mitigation, and machine learning, my non-work interests range widely from information theory (go Shannon!), quantum computing, grandfather paradox, Star Trek, Little Mermaid, 'why is the grass green?', 1Q84, etc., etc., etc. If you want to talk about, well, anything - just ping me.

### %20fy the string

Given a string1, replace all spaces with %20. Assume that the string has sufficient space at the end to hold additional characters. Also,...… Continue reading

#### String Permuations

Published on December 01, 2016

#### Reverse String

Published on December 01, 2016