[LeetCode] 443. String Compression

1. Question

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".

2. Thoughts

For ex) ["a","a","b","b","c","c","c"]

1. Make 3 pointers: cur_index(=where to save), cur_char(=what to count), and cur_char_count(=count on cur_char).

2. traverse through list.
   2-1 If the char == cur_char, simply ++ cur_char_count
   2-2 Else, save the cur_char, and cur_char_count to the list at cur_index.Then, update cur_char to the new char, and initialize cur_char_count to 1.

3. Because saving is done when change happen, make changes for the last element.(save data to the list)

3. Tips learned

4. My solution

class Solution:
    def compress(self, chars: List[str]) -> int:
        cur_char = chars[0]

        # cur_index = index in chars, cur_count_index = how many times cur_char is counted
        cur_index, cur_count_index = 0, 1
        index = 1
        while index < len(chars):
            # New char
            if chars[index] != cur_char:
                chars[cur_index] = cur_char
                cur_index += 1

                if cur_count_index != 1:
                    for count_index in range(len(str(cur_count_index))):
                        chars[cur_index] = str(cur_count_index)[count_index]
                        cur_index += 1

                cur_char = chars[index]
                cur_count_index = 1
            # Same char
            else:
                cur_count_index += 1

            index += 1

        chars[cur_index] = cur_char
        cur_index += 1

        if cur_count_index != 1:
            for count_index in range(len(str(cur_count_index))):
                chars[cur_index] = str(cur_count_index)[count_index]
                cur_index += 1

        return cur_index

Accepted
75/75 cases passed (59 ms)
Your runtime beats 96.58 % of python3 submissions
Your memory usage beats 16.32 % of python3 submissions (16.5 MB)

5. AI Solution and Improvements

Here's an optimized version of your code:

class Solution:
    def compress(self, chars: List[str]) -> int:
        write_index = 0 # Position to overwrite the original chars array
        read_index = 0  # Position to read the original chars array
        
        while read_index < len(chars):
            char = chars[read_index]
            count = 0
            
            # Count the consecutive characters
            while read_index < len(chars) and chars[read_index] == char:
                read_index += 1
                count += 1
            
            # Write the character
            chars[write_index] = char
            write_index += 1
            
            # Write the count if greater than 1
            if count > 1:
                for digit in str(count):
                    chars[write_index] = digit
                    write_index += 1
                    
        return write_index

Changes Made:

1. More Pythonic Way of Counting: Instead of keeping track of characters and counts separately, I've used a nested loop that counts consecutive characters in a more straightforward way.
2. Simplified Indexing: I've replaced the need for cur_char, cur_index, cur_count_index, and index with two indexes read_index and write_index. This simplifies the logic and makes it easier to understand.
3. Single Loop for Writing Characters and Counts: I've combined the logic for writing characters and counts into one place, reducing redundancy.

This revised code follows the same logic, but it's simplified and more Pythonic. It's still in constant extra space and linear time complexity.