LeetCode 443. String Compression

Intuition

Solution becomes simpler if you divide the reading pointer and writing pointer

1. loop through chars and do another loop inside to count number of occurrence of char
2. write the letter to write pointer
3. write each digits of count and increment write pointer accordingly if count is greater than 1

Optimal Solution

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

		 while i < len(chars):
            curr = chars[i]
            count = 0

            while i < len(chars) and chars[i] == curr:
                i += 1
                count += 1

            chars[write] = curr
            write += 1

            if count > 1:
                for digit in str(count):
                    chars[write] = digit
                    write += 1

        return write

Time Complexity

Time Complexity O(N)

Space Complexity O(1)