Optimize compression for in-place

Question

Given a string, implement an in-place algorithm to optimize its compression by replacing consecutive repeated characters with a single character followed by the count of repetitions. The function should return the length of the modified string and modify the input string directly. For example, given the input "aabbcc", the output should be "a2b2c2" with a length of 6.

Codemia · Accepted Answer

The problem requires us to compress a string by replacing consecutive repeated characters with a single character followed by the count of repetitions. This can be efficiently solved using the **two pointers** technique. The first pointer (`read`) will traverse the string to read characters, while the second pointer (`write`) will keep track of the position where we will write the compressed characters. This approach allows us to modify the string in-place, which is essential to meet the problem's requirements. 1. Initialize `write` pointer to 0, which will track the position to write compressed characters. 2. Use a `read` pointer to iterate through the string. 3. For each character, count its consecutive occurrences. 4. Write the character at the `write` position, followed by the count (if greater than 1). 5. Move the `write` pointer appropriately after writing the character and count. 6. Continue until the `read` pointer reaches the end of the string. 7. Finally, truncate the string to the length indicated by the `write` pointer. **Example:** For the input "aabbcc": - Start with `read` at index 0 ('a'), count 2, write 'a' at index 0, then write '2' at index 1. - Move `write` to index 2, then repeat for 'b' and 'c'. - Final output: "a2b2c2" with length 6. ```python def compress_string(s: str) -> int: if not s: return 0 write = 0 # Pointer for writing compressed characters read = 0 # Pointer for reading characters n = len(s) while read < n: current_char = s[read] count = 0 # Count occurrences of the current character while read < n and s[read] == current_char: read += 1 count += 1 # Write the character to the write position s = s[:write] + current_char + s[write+1:] write += 1 # Write the count if greater than 1 if count > 1: s = s[:write] + str(count) + s[write+1:] write += 1 # Truncate the string to the new length return write ``` The time complexity of this algorithm is **O(n)**, where n is the length of the string. This is because we make a single pass through the string with the `read` pointer, counting characters. The space complexity is **O(1)** in terms of additional space used, as we are modifying the string in-place without requiring extra data structures. 1. **Empty String**: If the input string is empty, the function should return 0. 2. **Single Character**: If the string contains only one character (e.g., "a"), the output should be the same character with a length of 1. 3. **All Unique Characters**: For a string like "abcde", the output should simply be "abcde" with a length of 5, since there are no consecutive characters to compress. 4. **All Same Characters**: For a string like "aaaa", the output should be "a4" with a length of 2.

Optimize compression for in-place

Lyft

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

Lyft Machine Learning 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