Given an array of characters, compress it in-place.

The length after compression must always be smaller than or equal to the original array.

Every element of the array should be a character (not int) of length 1.

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

 

Follow up:
Could you solve it using only O(1) extra space?

 

Example 1:

Input:
["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:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

# -*- coding:utf-8 -*-
__author__ = 'yangxin_ryan'
"""
Solutions:
这里的思路使用两个指针：
i作用是记录更改后chars的长度，
j作用是记录当前chars的下标位置，
count 为需要重复的次数，
当字符串结束后通过移动指针i，将count写入chars，
最后返回i的位置，就是新的字符串的长度。
"""


class StringCompression(object):

    def compress(self, chars):
        n = len(chars)
        i, count = 0, 1
        for j in range(1, n + 1):
            # 当前后一个 j 与 j - 1 字符是相等的
            if j < n and chars[j] == chars[j - 1]:
                count += 1
            else:
                # 字符不同，这里更新移动的指针
                chars[i] = chars[j - 1]
                i += 1
                if count > 1:
                    # 根据遍历的长度增加i的大小
                    for k in str(count):
                        chars[i] = k
                        i += 1
                count = 1
        return i