algoadvance

Leetcode 443. String Compression

Problem Statement:

Given an array of characters chars, compress it in-place such that the length of the compressed string is reduced. The compression algorithm should use the following rules:

1. For a group of repeated characters chars[i]...chars[j], it should be replaced by chars[i] followed by the number of consecutive characters if the group length is greater than 1.
2. The initial length of the array is significant, and the array should be modified in-place with O(1) extra space.
3. The function should return the new length of the compressed array.

Example:

• Input: chars = ['a','a','b','b','c','c','c']
• Output: Return 6, and the first 6 characters of the array should be: ['a','2','b','2','c','3']

Clarifying Questions:

1. Q: What is the maximum length of the input array chars? A: You can assume chars has length at most 2000.

2. Q: Should the characters in the array be only lowercase alphabets? A: The problem doesn’t specify a restriction, so let’s assume it can be any valid character.

3. Q: Is it necessary to use O(1) extra space? A: Yes, the modification should be done in-place with O(1) extra space.

Strategy:

1. Use two pointers, one for reading read and the other for writing write.
2. Iterate through the chars array with the read pointer to identify groups of repeated characters.
3. For each group of repeated characters, write the character and then the number of repetitions (if more than 1) using the write pointer.
4. Continue until the end of the array is reached.

Code:

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int compress(vector<char>& chars) {
        int write = 0, read = 0;
        int n = chars.size();
        
        while (read < n) {
            char currentChar = chars[read];
            int count = 0;
            
            // Count the number of consecutive characters
            while (read < n && chars[read] == currentChar) {
                read++;
                count++;
            }
            
            // Write the character
            chars[write++] = currentChar;
            
            // Write the count if more than 1
            if (count > 1) {
                for (char c : to_string(count)) {
                    chars[write++] = c;
                }
            }
        }
        
        return write;
    }
};

Explanation:

1. while (read < n): Iterate through the array until the end.
2. char currentChar = chars[read]: Store the current character.
3. while (read < n && chars[read] == currentChar): Count the number of consecutive occurrences of currentChar.
4. chars[write++] = currentChar: Write the current character to the write position and increment write.
5. if (count > 1): If the count of consecutive characters is more than 1, convert the count to a string, and then write each digit to the write position.
6. Finally, return write, which stores the new length of the compressed array.

Time Complexity:

• The time complexity of this solution is O(n), where n is the length of the chars array. This is because we traverse the array a constant number of times (each element is visited once).
• The space complexity is O(1) auxiliary space, as we are modifying the array in place and not using any additional data structures apart from a few variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?