Optimize compression for without recursion

Question

Given a string, optimize the compression of consecutive characters without using recursion. Your solution should replace sequences of the same character with the character followed by the count of its occurrences, and return the compressed string. For example, the input "aaabbc" should return "a3b2c1".

Codemia · Accepted Answer

The problem requires us to compress a string by replacing consecutive characters with the character followed by its count. This is a classic example of using a linear traversal technique, which can be efficiently handled using a **two-pointer approach**. We can maintain a single pointer to track the current character and another to traverse through the string. This approach is suitable here because we need to iterate through the string in a single pass, counting consecutive characters without the need for additional recursive calls.

1. Initialize an empty list to build the compressed string and a count variable to count occurrences of each character.
2. Use a loop to iterate through the string. For each character:
   - If it matches the previous character, increment the count.
   - If it does not match, add the previous character and its count to the list, then reset the count for the new character.
3. After the loop, handle the last character and its count.
4. Join the list into a single string and return it.

**Example:** For the input 'aaabbc':
- Start with 'a', count is 1. Next character is 'a', count becomes 2. Next 'a', count becomes 3.
- Next character is 'b', add 'a3' to the list, reset count for 'b' to 1.
- Next character is 'b', count becomes 2. Next 'c', add 'b2' to the list, reset count for 'c' to 1.
- Finally, add 'c1' to the list. The output is 'a3b2c1'.

Here is the Python implementation of the approach:
```python
def compress_string(s):
    if not s:
        return ''  # Edge case for empty string

compressed = []
    count = 1
    prev_char = s[0]

for i in range(1, len(s)):
        if s[i] == prev_char:
            count += 1
        else:
            compressed.append(f'{prev_char}{count}')
            prev_char = s[i]
            count = 1

# Handle the last character
    compressed.append(f'{prev_char}{count}')

return ''.join(compressed)
```
This code iteratively compresses the string without using recursion.

The time complexity of this solution is **O(n)**, where n is the length of the input string. This is because we make a single pass through the string to compress it. The space complexity is **O(n)** in the worst case, where every character is unique and we store each character along with its count. Given the constraints, this is efficient and manageable.

1. **Empty string**: Input '' should return '' since there are no characters to compress.
2. **Single character**: Input 'a' should return 'a1' since it occurs once.
3. **All characters the same**: Input 'aaaa' should return 'a4' as there's only one unique character.
4. **Different characters**: Input 'abc' should return 'a1b1c1' since each character appears once.
5. **Large input**: Testing with a very long string of repeated characters should ensure performance remains efficient and no stack overflow occurs, confirming we stay within the linear approach.

Optimize compression for without recursion

Slack

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

Slack 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