Python Two Pointers - O(n) time O(1) space


  • 2
    1. Group the array into repeated chunks, keeping track of the character and the count. This forms the encoded contents.
    2. Update the original array with the encodede contents. We maintain a left pointer to know which position to update the original array with the encoded contents and increment it according to the length of the encoded contents.

    The encoded contents will definitely be shorter than the original contents, so we can overwrite the original without worries.

    - Yangshun

    class Solution(object):
        def compress(self, chars):
            left = i = 0
            while i < len(chars):
                char, length = chars[i], 1
                while (i + 1) < len(chars) and char == chars[i + 1]:
                    length, i = length + 1, i + 1
                chars[left] = char
                if length > 1:
                    len_str = str(length)
                    chars[left + 1:left + 1 + len(len_str)] = len_str
                    left += len(len_str)
                left, i = left + 1, i + 1
            return left
    

  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.