algoadvance

Leetcode 443. String Compression

Problem Statement

Given an array of characters chars, compress it in-place. The length after compression must always be smaller than or equal to the original array. Every element of the array should be a single character not a string of length 1.

The compressed string should be returned in the form of a new length of the array.

After you are done modifying the input array in-place, return the new length of the array.

The input array is a list of characters. Each character should be compressed as per the following rules:

• If a character appears consecutively more than once, it should be replaced by the character followed by the number of times it consecutively appears.
• If a character appears only once, it remains as is and is not followed by a number.

Example

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

Input: chars = ["a"]
Output: Return 1, and the first 1 character of the input array should be: ["a"]

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"]

Clarifying Questions

1. Q: Are the input arrays always non-empty? A: Yes, you can assume the input array has at least one character.

2. Q: What should be done if the compressed length is longer than the original length? A: The problem guarantees that the compressed length will not be longer than the original length.

3. Q: Should the returned length consider only the compressed array or the entire size of the array including trailing unused elements? A: The returned length should consider only the compressed array.

Strategy

• Use two pointers: write will track where to write the compressed result and read will iterate over the characters.
• Use a loop to count consecutive characters.
• Compress each group of consecutive characters by writing the character followed by its count if greater than 1.
• Convert the count to characters and write them into the array.
• Once processed all characters, return the write pointer value as the new length.

Time Complexity

• Time Complexity: O(n), where n is the length of the chars array. Each character is read and written at most once.
• Space Complexity: O(1), as we’re modifying the array in place and using a constant amount of extra space.

Code

public class Solution {
    public int compress(char[] chars) {
        int write = 0, read = 0;
        while (read < chars.length) {
            char currentChar = chars[read];
            int count = 0;

            // Count occurrence of the character
            while (read < chars.length && chars[read] == currentChar) {
                read++;
                count++;
            }

            // Write the character
            chars[write++] = currentChar;

            // Write the count if greater than 1
            if (count > 1) {
                for (char c : Integer.toString(count).toCharArray()) {
                    chars[write++] = c;
                }
            }
        }
        return write;
    }
}

Explanation

• write is the index at which to write the next element.
• read is the current index being read.
• The outer while loop continues until all characters in the array have been processed.
• Count occurrences of the current character currentChar using the inner while loop.
• Write each character and its count (if greater than 1) to chars array at the write position(s).
• Convert count to characters by transforming it into a string and then iterating over the string’s characters to write them into chars.
• Finally, return write which indicates the new length of the compressed string.

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?