443. String Compression

Easy

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?

😇 Solution

O(s)

class Solution:
    def stringCompression(s):
        i = 0
        ans = ''
        while(i < len(s)):
            count = 0
            c = s[i]
            while(c == s[i]):
                i += 1
                count += 1
                if i == len(s):
                    break
            ans += c
            if count != 1:
                ans += str(count)
        return ans if len(ans) <= len(s) else s
    
    def compress(self, chars: List[str]) -> int:
        
        s = ''
        for c in chars:
            s += c
        ans =  Solution.stringCompression(s)
        for i,a in enumerate(ans):
            chars[i] = a
        return len(ans)

O(s)

class Solution:
    def compress(self, chars: List[str]) -> int:
        
        anchor, write = 0,0
        for read,c in enumerate(chars):
            
            if read+1 == len(chars) or chars[read+1] !=c:
                chars[write] = chars[anchor]
                write += 1
                
                if read>anchor:
                    for digit in str(read-anchor+1):
                        chars[write] = digit
                        write += 1
                anchor = read + 1
                
        return write