algoadvance

Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that the compressed length must not exceed the length of the original array. You must modify the input array in place with the O(1) extra space allocation.

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

Examples

Example 1:

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"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"]
Output: Return 1, and the first character of the input array should be: ["a"]
Explanation: The only group is "a", which remains uncompressed as "a".

Example 3:

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"].
Explanation: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints

Clarifying Questions

  1. Can the chars array have non-alphabetical characters?
    • Yes, chars can include any characters including digits and symbols.
  2. What should be done if compression exceeds the original length?
    • It should not exceed the original length as per the problem statement and constraints.

Strategy

  1. Use two pointers: read (for reading original characters) and write (for writing the compressed characters).
  2. Iterate through the characters and count consecutive characters.
  3. Write the character to the write pointer, followed by the count if it is greater than 1.
  4. Move both pointers accordingly.
  5. Modify the input list in place and return the new length of the compressed list.

Time Complexity

The time complexity of this approach is O(n), where n is the length of the chars array, as we iterate through the list a single time.

Code

def compress(chars):
    # Initialize read and write pointers
    read, write = 0, 0
    
    while read < len(chars):
        # Record the current character and start of the group
        char = chars[read]
        count = 0
        
        # Count the number of occurrences of the character
        while read < len(chars) and chars[read] == char:
            read += 1
            count += 1
        
        # Write the character to the write pointer
        chars[write] = char
        write += 1
        
        # Write the count if more than 1
        if count > 1:
            for c in str(count):
                chars[write] = c
                write += 1
    
    return write

# Example usage:
chars = ["a","a","b","b","c","c","c"]
print(compress(chars))  # Output: 6
print(chars)  # Output: ["a","2","b","2","c","3"]

Try our interview co-pilot at AlgoAdvance.com