443.String Compression
===

###### tags: `Medium`,`Two Pointers`,`String`

[443. String Compression](https://leetcode.com/problems/string-compression/)

### 題目描述

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.

### 解答
#### Python

class Solution:
    def compress(self, chars: List[str]) -> int:
        i, j = 0, 1
        cur = 0

        while i < len(chars):
            while j < len(chars) and chars[i] == chars[j]:
                j += 1
            
            chars[cur] = chars[i]
            cur += 1
            
            if j - i == 1:
                i = j
                continue

            cnt = j - i
            nums = list(str(cnt))

            for num in nums:
                chars[cur] = num
                cur += 1

            i = j

        return cur

> [name=Ron Chen][time=Thr, Mar 2, 2023]
> 寫了才發現倒讚超多不是沒原因的= =

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)