Remove All Adjacent Duplicates in String II

Solution

Let $n$ be the string length.

Brute Force (TLE)

Complexity

time: $O(\frac{n^2}{k})$ (scan s no more than $\frac{n}{k}$ times)
space: $O(1)$

def removeDuplicates(self, s: str, k: int) -> str:
    n = -1
    while n != len(s):
        n = len(s)
        count = 1
        for i in range(n):
            if i == 0 or s[i] != s[i-1]:
                count = 1
            else:
                count += 1

            if count == k:
                s = s[:i-k+1] + s[i+1:]
                break
    return s

HashMap

Complexity

time: $O(n)$
space: $O(n)$

def removeDuplicates(self, s: str, k: int) -> str:
    i = 0
    counts = [0 for _ in range(len(s))]
    while i < len(s):
        if i == 0 or s[i] != s[i-1]:
            counts[i] = 1
        else:
            counts[i] = counts[i - 1] + 1
        
        if counts[i] == k:
            s = s[:i-k+1] + s[i+1:]
            i -= k
        
        i += 1

    return s

Stack

Complexity

time: $O(n)$
space: $O(n)$

def removeDuplicates(self, s: str, k: int) -> str:
    i = 0
    counts = []
    while i < len(s):
        if i == 0 or s[i] != s[i-1]:
            counts.append(1)
        else:
            counts[-1] += 1
            
        if counts[-1] == k:
            counts.pop()
            s = s[:i-k+1] + s[i+1:]
            i -= k

        i += 1
    return s

Two Pointers

Complexity

time: $O(n)$
space: $O(n)$

def removeDuplicates(self, s: str, k: int) -> str:
    s = list(s)
    j = 0
    counts = []
    for i in range(len(s)):
        s[j] = s[i]
        if j == 0 or s[j] != s[j - 1]:
            counts.append(1)
        else:
            counts[-1] += 1
        
        if counts[-1] == k:
            counts.pop()
            j -= k
        j += 1
    return "".join(s[:j])