Introduction

In this blog post, we will explore how to solve the LeetCode problem "443" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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: If the group's length is 1, append the character to s. Otherwise, append the character followed by the group's length. The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars. After you are done modifying the input array, return the new length of the array. You must write an algorithm that uses only constant extra space. 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 since it's a single character. 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: 1 <= chars.length <= 2000 chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

Explanation

Here's the breakdown of the solution:

• Iterate and Count: Traverse the input array, keeping track of consecutive repeating characters and their counts.
• In-Place Modification: When a different character is encountered or the end of the array is reached, update the input array chars with the character and its count (if the count is greater than 1).

• Handle Multi-Digit Counts: If the count is 10 or more, convert it to a string and add each digit as a separate character to the chars array.

• Runtime Complexity: O(n), where n is the length of the input array.

• Storage Complexity: O(1) (constant extra space).

Code

    def compress(chars: list[str]) -> int:
    """Compresses an array of characters in-place.

    Args:
        chars: The array of characters to compress.

    Returns:
        The new length of the compressed array.
    """

    n = len(chars)
    if n == 0:
        return 0

    write_index = 0
    read_index = 0

    while read_index < n:
        char = chars[read_index]
        count = 0
        while read_index < n and chars[read_index] == char:
            read_index += 1
            count += 1

        chars[write_index] = char
        write_index += 1

        if count > 1:
            for digit in str(count):
                chars[write_index] = digit
                write_index += 1

    return write_index