443. String Compression

Description

The problem is to compress a list of characters by converting consecutive duplicate characters into the character followed by the number of occurrences. The compressed list must be stored in-place, and the function should return the new length of the list after compression. If a character appears only once, it is simply kept without appending any count.

Intuition

The intuition behind this problem is that we can iterate through the list and count the occurrences of each character. As we move through the list, we can replace the characters in-place with the compressed format (character + count) if the count is greater than 1. This allows us to compress the string while keeping the space complexity minimal.

Approach

1. Initialize two pointers: i for placing the compressed characters in the list and j for iterating through the list.
2. For each character in the list: - Count how many times the character repeats consecutively. - Replace the character at the i position in the list with the current character. - If the character repeats more than once, convert the count to a string and add each digit to the list at subsequent positions. - Move the pointer i accordingly.
3. Continue this process until all characters have been processed.
4. The length of the compressed list is the value of i at the end.

Complexity

Time Complexity:

The time complexity is (O(n)), where (n) is the length of the list. This is because we traverse the list once and perform a constant amount of work for each character.

Space Complexity:

The space complexity is (O(1)) because we modify the list in place and do not use any extra space proportional to the input size.

Code

C++

class Solution {
public:
    int compress(vector& chars) {
        int i = 0;
        int j = 0;
        while (j < chars.size()) {
            int count = 0;
            char curr = chars[j];
            
            while (j < chars.size() && chars[j] == curr) {
                j++;
                count++;
            }
            chars[i++] = curr;
            if (count > 1) {
                for (char digit : to_string(count)) {
                    chars[i++] = digit;
                }
            }
        }
        return i;
    }
};

Python

class Solution:
    def compress(self, chars: List[str]) -> int:
        i = 0
        j = 0
        while j < len(chars):
            count = 0
            curr = chars[j]
            
            while j < len(chars) and chars[j] == curr:
                j += 1
                count += 1
                
            chars[i] = curr
            i += 1
            if count > 1:
                for digit in str(count):
                    chars[i] = digit
                    i += 1
                    
        return i

Java

class Solution {
    public int compress(char[] chars) {
        int i = 0;
        int j = 0;
        while (j < chars.length) {
            int count = 0;
            char curr = chars[j];
            
            while (j < chars.length && chars[j] == curr) {
                j++;
                count++;
            }
            chars[i++] = curr;
            if (count > 1) {
                for (char digit : Integer.toString(count).toCharArray()) {
                    chars[i++] = digit;
                }
            }
        }
        return i;
    }
}

JavaScript

var compress = function (chars) {

    let i = 0;
    let j = 0;
    while (j < chars.length) {
        let count = 0;
        let curr = chars[j];
        
        while (j < chars.length && chars[j] === curr) {
            j++;
            count++;
        }
        chars[i++] = curr;
        if (count > 1) {
            for (let digit of count.toString()) {

                chars[i++] = digit;
            }
        }
    }
    return i;
};