0% completed

Solution: Remove All Adjacent Duplicates in String II

Problem Statement

You are given a string s and an integer k. Your task is to remove groups of identical, consecutive characters from the string such that each group has exactly k characters. The removal of groups should continue until it's no longer possible to make any more removals. The result should be the final version of the string after all possible removals have been made.

Examples

- Input: s = "abbbaaca", k = 3
- Output: "ca"
- Explanation: First, we remove "bbb" to get "aaaca". Then, we remove "aaa" to get "ca".
- Input:

.....

Like the course? Get enrolled and start learning!

Mohammed Dh Abbas

· 2 years ago

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        for index, char in enumerate(s):
            # if we have reached k count for the same character
            if len(stack) > 0 and char == stack[-1][0] and stack[-1][1] == k - 1:
                # keep popping
                count = 0
                while count < k - 1:
                    count += 1
                    stack.pop()
            else: # push the character
                # if pervious character is the same as the character from the loop
                if len(stack) > 0 and char == stack[-1][0]:
                    stack.append((char, stack[-1][1] + 1))
                else:
                    stack.append((char, 1))
        return "".join([x for x,y in stack]);

Ben

· 2 years ago

Show 1 reply

L

lejafilip

· 2 years ago

P

Pete Stenger

· 2 years ago

This solution doesn't need to reconstruct the counts.

        stack = []
        for c in s:
            if stack and stack[-1][-1] == c:
                stack[-1] += c
            else:
                stack.append(c)
            
            if stack and len(stack[-1]) == k:
                stack.pop()

        return "".join(stack)

Nghĩa Huỳnh Trung

· a year ago

func (this *Solution) removeDuplicates(str string, k int) string {
    stack := []rune{}
    for _, rune := range str {
        count := 0
        for len(stack) > count && rune == stack[len(stack)-count-1] {
            count++
        }
        if count == k-1 {
            stack = stack[:len(stack)-k+1]
            continue
        }
        stack = append(stack, rune)

    }
    return string(stack)
}

Omotola Awofolu

· 2 months ago

arr = []
for char in s:
    temp = [char]
    while arr and char == arr[-1] and len(temp) < k:
        temp.insert(0,arr.pop())
    if len(temp) < k:
        arr.extend(temp)
 return "".join(arr)

Dhaval Bhimani

· 25 days ago