Problem statement

https://leetcode.com/problems/string-compression/

Solution

Just iterate element by element and check look for group of repeating elements. We will use beg and end pointers for the start and for the end of group of equal elements. On each iteration we first look group, then write S[beg] = char and finally write frequency of this symbol just after.

Complexity

Time complexity is O(n), space complexity is O(1)

Code

class Solution:
    def compress(self, S):
        beg, end = 0, 0
        n = len(S)
        
        while end < n:
            char, size = S[end], 1
            while end + 1 < n and char == S[end + 1]:
                size, end = size + 1, end + 1
                
            S[beg] = char
            
            if size > 1:
                len_str = str(size)
                S[beg + 1:beg + 1 + len(len_str)] = len_str
                beg += len(len_str)
            beg, end = beg + 1, end + 1
        return beg