Optimize compression for in-place

Question

Given a string of characters, implement an in-place algorithm to optimize the compression of the string such that consecutive repeated characters are replaced by a single instance of the character followed by the count of repetitions. The function should return the length of the compressed string and modify the input string to reflect the compressed form. For example, given the input "aabbcc", the output should be 6, and the modified string should be "a2b2c2".

Codemia · Accepted Answer

The problem at hand involves compressing a string in-place by replacing consecutive repeated characters with a single instance of the character followed by the count of repetitions. The appropriate pattern for this problem is the **two pointers technique**. One pointer will track the position where we will write the compressed characters, while the other pointer will iterate through the string to count consecutive characters. This approach is efficient because it allows us to traverse the string only once and modify it in-place, thus saving space and time.

1. Initialize two pointers: `read` (to read through the string) and `write` (to write the compressed form). Set `write` at the start of the string.
2. Use a loop to traverse the string using `read`. For each character, count how many times it appears consecutively by incrementing a `count` variable.
3. Once the end of a sequence is reached, write the character at the `write` pointer, followed by the count if it's greater than 1.
4. Move the `write` pointer forward by 1 for the character, and by the length of the count if it's greater than 1.
5. Continue until the entire string is processed.
6. Finally, return the length of the compressed string, which is represented by the `write` pointer.

**Example:** For the input "aabbcc":
- Read 'a', count 2, write 'a' and '2' at positions 0 and 1. (string becomes 'a2bbcc')
- Read 'b', count 2, write 'b' and '2' at positions 2 and 3. (string becomes 'a2b2cc')
- Read 'c', count 2, write 'c' and '2' at positions 4 and 5. (string becomes 'a2b2c2')

Here’s the Python code implementing the described approach:

```python
def compress(chars):
    write = 0
    read = 0
    n = len(chars)

while read < n:
        char = chars[read]
        count = 0
        # Count occurrences of char
        while read < n and chars[read] == char:
            read += 1
            count += 1
        # Write the character
        chars[write] = char
        write += 1
        # Write the count if more than 1
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1

return write
```

This code efficiently compresses the input string in-place and returns the new length.

The time complexity of this algorithm is **O(N)** where N is the length of the input string, as we traverse the string once. The space complexity is **O(1)** because we are modifying the input string in-place without needing additional data structures for storage.

1. **Empty String:** If the input string is empty, the output should be 0, and the string remains unchanged.
2. **Single Character:** For input such as "a", the output should be 1, with the string also unchanged.
3. **All Unique Characters:** For input like "abcdef", the output should be 6, with the string unchanged as there are no repetitions.
4. **Large Counts:** For input like "aaabbc", the output should be 6, and the string should become "a3b2c". This tests the algorithm’s ability to handle higher counts.

Optimize compression for in-place

Netflix

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

Netflix 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