Compress Consecutive Characters with Run Lengths

Question

This question asks the candidate to implement a function that compresses a string by replacing consecutive characters with their counts, known as run-length encoding.

Codemia · Accepted Answer

To solve the problem of compressing consecutive characters, we will iterate through the string while keeping track of the current character and its count. Whenever we encounter a different character, we will append the current character and its count to the result string. This process will continue until we have traversed the entire string.

Here is a Python implementation of the run-length encoding algorithm:

```python
def compress_string(s: str) -> str:
    if not s:
        return ""
    result = []
    count = 1
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            result.append(s[i - 1] + str(count))
            count = 1
    result.append(s[-1] + str(count))  # Append the last character and its count
    return ''.join(result)
```
This function iterates through the string once, maintaining a count of consecutive characters and appending the compressed format to a result list.

The time complexity of this solution is O(n), where n is the length of the input string, as we are traversing the string once. The space complexity is O(n) in the worst case, where all characters are unique, resulting in a maximum size for the output string.

It is important to consider edge cases such as an empty string input, which should return an empty string. Additionally, we should test with strings that consist of a single character, strings with no consecutive characters, and very long strings to ensure the algorithm performs efficiently.

To validate our solution, we can run several test cases:
1. `compress_string('aaabbc')` should return `'a3b2c1'`.
2. `compress_string('abcd')` should return `'a1b1c1d1'`.
3. `compress_string('')` should return `''`.
4. `compress_string('aaaaaa')` should return `'a6'`.

Compress Consecutive Characters with Run Lengths

Oracle

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Oracle 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