Problem statement : Write a function to Compress a given string. Only return the compressed string if it saves space.
Difficulty level: Easy
Test Cases
- 'AAABAACCDDDD' ---> 'A3BA2C2D4'
- 'BAAACCDDDD' ---> 'BA3C2D4'
- 'AABBCC' --> 'AABBCC'
- 'BBBAACCCCDD' --> 'B3A2C4D2'
Algorithm
- Setup a pointer at first character of string, initialise an empty string and a counter.
- Iterate through the string and check if character is equal to the first character of the string.
- if both are equal increment counter.
-
Else,
- add the first character and it's count to result string.
- if count is greater than 1 then only add count to the result string.
- Else, add an empty string to the result string.
- now, the first character will be the current character.
- reset the counter value to 1.
- add the first character and it's count to result string.
Add the last character and it's count to result string.
Return the resultant compressed string if it's length is less than the given string, else return the given string.
Time and Space Complexity
- Time complexity: O(n)
- Space complexity: O(n)
Code
class CompressString(object):
def compress(self, input):
if input is None or not input:
return input
result = ''
count = 0
prev_char = input[0]
for char in input:
if char == prev_char:
count += 1
else:
result += prev_char + (str(count) if count > 1 else '')
prev_char = char
count = 1
result += prev_char + (str(count) if count > 1 else '')
return result if len(result) < len(input) else input
More precise compression
class CompressString(object):
def compress(self, input):
if input is None or not input:
return input
result = ''
count = 0
prev_char = input[0]
for char in input:
if char == prev_char:
count += 1
else:
if count > 2:
result += prev_char + (str(count))
prev_char = char
count = 1
elif count == 1:
result += prev_char
count = 1
prev_char = char
else:
result += prev_char
result += prev_char
count = 1
prev_char = char
result += prev_char + (str(count) if count > 2 else prev_char)
return result if len(result) < len(input) else input
Test
import unittest
from compressString import CompressString
class TestCompress(unittest.TestCase):
def testCompress(self, func):
self.assertEqual(func(None), None)
self.assertEqual(func(''), '')
self.assertEqual(func('AABBCC'), 'AABBCC')
self.assertEqual(func('AAABCCDDDDE'), 'A3BC2D4E')
self.assertEqual(func('BAAACCDDDD'), 'BA3C2D4')
self.assertEqual(func('AAABAACCDDDD'), 'A3BA2C2D4')
print('Success: testCompress')
def main():
test = TestCompress()
compress_string = CompressString()
test.testCompress(compress_string.compress)
if __name__ == '__main__':
main()
Top comments (3)
Simple improvement proposal: you could remove the last check by replacing chars only if there are more than 2 in a row.
Replacing 'CC' with 'C2' never saves space. Replacing more than 2 characters always saves space. So you would either return the same input string or return compressed string that's shorter than original.
I could do something like if count is more than 2 than add the character with count, if count is 1, than only add the character , and lastly if count is exactly 2, then add the character 2 times, so it would remain same as original string.
I didn't know that, looks really neat. Thanks for the tip. 🌟