Optimize compression for O(1) space

Question

Given a string, optimize the compression of its characters such that the resulting compressed string uses O(1) space. The output should be the length of the compressed string, and the characters should be stored in the original string itself. For example, if the input is "aabbcc", the output should be 6, as the compressed form would be "a2b2c2".

Codemia · Accepted Answer

The task is to compress a string in such a way that we count consecutive characters and replace them with the character followed by its count. The output length is the length of this compressed string. Given that we need to use O(1) space for the compression, we cannot use extra data structures like arrays or lists to hold the counts of characters. Instead, we will modify the original string in place. This problem can be solved using a two-pointer technique where one pointer iterates through the string to read characters, and the other pointer is used to write the compressed format back into the string. 1. Initialize a write pointer `write_index` to 0, which will point to the position in the string where the next character or its count will be written. 2. Use a read pointer `read_index` to traverse through the string. For each character at `read_index`, count how many times it appears consecutively. 3. Write the character at `write_index`, then if the count is greater than 1, convert the count to a string and write each digit at subsequent positions starting from `write_index + 1`. 4. Move `write_index` accordingly after writing the character and its count. 5. Continue until the end of the string is reached, and return the length of the compressed string, which will be `write_index`. ```python def compress_string(s: str) -> int: if not s: return 0 write_index = 0 read_index = 0 n = len(s) while read_index < n: char = s[read_index] count = 0 while read_index < n and s[read_index] == char: read_index += 1 count += 1 # Write character s = s[:write_index] + char + s[write_index + 1:] write_index += 1 # Write count if greater than 1 if count > 1: for digit in str(count): s = s[:write_index] + digit + s[write_index + 1:] write_index += 1 return write_index ``` The time complexity of this algorithm is O(n), where n is the length of the input string. This is because we traverse the string once to read the characters and potentially write back compressed characters and counts. The space complexity is O(1) since we are modifying the string in place without utilizing any additional data structures. 1. Empty String: If the input string is empty (`s = ''`), the output should be 0 since there are no characters to compress. 2. Single Character: If the input string has a single character (`s = 'a'`), the result should be 1, as it remains 'a'. 3. All Characters Unique: If the string consists of unique characters (`s = 'abcdef'`), the output length should equal the input length, which is 6. 4. Large Counts: For a string like `s = 'aaabbbcc'`, the output should correctly reflect `a3b3c2`, resulting in a length of 6.

Optimize compression for O(1) space

Doordash

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Doordash Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string