string_compression.py

"""
String compression

You are given an array of characters chars, consisting of letters or numbers. Implement a data compression algorithm that modifies the original array as follows:

If a group of consecutive characters is repeated once, it remains unchanged.
If a group is repeated more than once, the character is replaced by the character itself, followed by the length of the group.
Return the new length of the array after compression.

Notes:

A group is a sequence of one or more identical characters in a row.
Group lengths greater than 9 must be broken into individual digits. For example, 12 is written as ["1","2"].
The array modification must happen in place - you cannot allocate additional memory for arrays.
After the new length, the contents of the array do not matter (the system will only check elements up to this length).

Example 1

Input: chars = ["a","a","b","b","c","c","c"]

Output: return 6, and the first 6 characters in the chars array should be ["a","2","b","2","c","3"].

Explanation: the groups are "aa", "bb", "ccc". After compression, we get "a2b2c3".

Example 2

Input: chars = ["a"]

Output: return 1, and the chars array remains ["a"].

Explanation: the only group is "a", and it remains unchanged.

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 in the chars array should be ["a","b","1","2"].

Explanation: groups are "a", "bbbbbbbbbbbb". After compression, we get "ab12".
Limitations

1 <= chars.length <= 2000
chars[i] — a Latin letter (upper or lower case), a digit, or a symbol.
"""

class Solution:

  def calc_substitution(self, char, cur_count):
        result = [char]
        if cur_count > 1:
            cur_count_list = list(str(cur_count))
            result.extend(cur_count_list)
        
        return result
      
    
  def compress(self, chars: list[str]) -> int:
        
        prev_char = None
        cur_count = 0
        index = 0
        rewrite_index = 0
        new_length = 0
        
        while index < len(chars):
            cur_char = chars[index]
            
            if index == 0:
                prev_char = cur_char
                
            if prev_char == cur_char:
                cur_count += 1
            else:
                # overwrite on the go
                substitution = self.calc_substitution(prev_char, cur_count)
                substitution_len = len(substitution)
                chars[rewrite_index:rewrite_index+substitution_len] = substitution
                rewrite_index += substitution_len
                new_length += substitution_len
                
                prev_char = cur_char
                cur_count = 1
            
            index += 1
        
        
        # overwrite on the go (the last chunk)
        substitution = self.calc_substitution(prev_char, cur_count)
        substitution_len = len(substitution)
        chars[rewrite_index:rewrite_index+substitution_len] = substitution
        rewrite_index += substitution_len
        new_length += substitution_len
        
        return new_length