1209. Remove All Adjacent Duplicates In String II - Explanation

Description

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example 1:

Input: s = "abcd", k = 2

Output: "abcd"

Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3

Output: "aa"

Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2

Output: "ps"

Constraints:

1 <= s.length <= 100,000
2 <= k <= 10,000
s only contains lowercase English letters.

Topics

String Stack

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Stack Data Structure - Tracking consecutive character counts and efficiently handling removals
Two Pointers - Using read and write pointers to modify strings in-place
String Manipulation - Working with mutable character arrays and substring operations

1. Brute Force

Intuition

The most direct approach is to repeatedly scan the string looking for k consecutive identical characters. When found, we remove them and restart the scan from the beginning since the removal might create new groups of k adjacent duplicates.

This process continues until a full scan completes without finding any group to remove. While straightforward, this approach is inefficient because each removal requires rescanning from the start.

Algorithm

Convert the string to a mutable format (list or character array).
Repeatedly scan the string:
- Track the current character and count consecutive occurrences.
- When the count reaches k, remove those characters from the string, set a flag, and restart the scan.
If a full scan completes without any removal, exit the loop.
Return the resulting string.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        while s:
            flag = False
            cur = s[0]
            cnt = 1
            for i in range(1, len(s)):
                if cur != s[i]:
                    cnt = 0
                    cur = s[i]
                cnt += 1
                if cnt == k:
                    s = s[:i - cnt + 1] + s[i + 1:]
                    flag = True
                    break

            if not flag:
                break

        return s

public class Solution {
    public String removeDuplicates(String s, int k) {
        while (s.length() != 0) {
            boolean flag = false;
            char cur = s.charAt(0);
            int cnt = 1;

            for (int i = 1; i < s.length(); i++) {
                if (cur != s.charAt(i)) {
                    cnt = 0;
                    cur = s.charAt(i);
                }
                cnt++;
                if (cnt == k) {
                    s = s.substring(0, i - cnt + 1) + s.substring(i + 1);
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                break;
            }
        }

        return s;
    }
}

class Solution {
public:
    string removeDuplicates(string s, int k) {
        while (s.length()) {
            bool flag = false;
            char cur = s[0];
            int cnt = 1;

            for (int i = 1; i < s.size(); i++) {
                if (cur != s[i]) {
                    cnt = 0;
                    cur = s[i];
                }
                cnt++;
                if (cnt == k) {
                    s = s.substr(0, i - cnt + 1) + s.substr(i + 1);
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                break;
            }
        }

        return s;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {string}
     */
    removeDuplicates(s, k) {
        while (s) {
            let flag = false;
            let cur = s[0];
            let cnt = 1;

            for (let i = 1; i < s.length; i++) {
                if (cur !== s[i]) {
                    cnt = 0;
                    cur = s[i];
                }
                cnt++;
                if (cnt === k) {
                    s = s.slice(0, i - cnt + 1) + s.slice(i + 1);
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                break;
            }
        }

        return s;
    }
}

public class Solution {
    public string RemoveDuplicates(string s, int k) {
        while (s.Length != 0) {
            bool flag = false;
            char cur = s[0];
            int cnt = 1;

            for (int i = 1; i < s.Length; i++) {
                if (cur != s[i]) {
                    cnt = 0;
                    cur = s[i];
                }
                cnt++;
                if (cnt == k) {
                    s = s.Substring(0, i - cnt + 1) + s.Substring(i + 1);
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                break;
            }
        }

        return s;
    }
}

func removeDuplicates(s string, k int) string {
    bytes := []byte(s)
    for len(bytes) > 0 {
        flag := false
        cur := bytes[0]
        cnt := 1

        for i := 1; i < len(bytes); i++ {
            if cur != bytes[i] {
                cnt = 0
                cur = bytes[i]
            }
            cnt++
            if cnt == k {
                bytes = append(bytes[:i-cnt+1], bytes[i+1:]...)
                flag = true
                break
            }
        }

        if !flag {
            break
        }
    }

    return string(bytes)
}

class Solution {
    fun removeDuplicates(s: String, k: Int): String {
        var str = StringBuilder(s)
        while (str.isNotEmpty()) {
            var flag = false
            var cur = str[0]
            var cnt = 1

            for (i in 1 until str.length) {
                if (cur != str[i]) {
                    cnt = 0
                    cur = str[i]
                }
                cnt++
                if (cnt == k) {
                    str.delete(i - cnt + 1, i + 1)
                    flag = true
                    break
                }
            }

            if (!flag) {
                break
            }
        }

        return str.toString()
    }
}

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        var arr = Array(s)
        while !arr.isEmpty {
            var flag = false
            var cur = arr[0]
            var cnt = 1

            for i in 1..<arr.count {
                if cur != arr[i] {
                    cnt = 0
                    cur = arr[i]
                }
                cnt += 1
                if cnt == k {
                    arr.removeSubrange((i - cnt + 1)...i)
                    flag = true
                    break
                }
            }

            if !flag {
                break
            }
        }

        return String(arr)
    }
}

Time & Space Complexity

Time complexity: $O(\frac {n ^ 2}{k})$
Space complexity: $O(n)$

2. Stack

Intuition

To avoid rescanning the entire string after each removal, we can use a stack to track consecutive counts as we process each character. When we encounter a character, we check if it matches the previous one. If so, we increment the count; otherwise, we start a new count.

When the count reaches k, we remove those k characters and continue from where we left off. The stack helps us remember the count before the removal so we can correctly continue counting if the characters before and after the removed segment match.

Algorithm

Convert the string to a mutable list and initialize an empty stack to track counts.
Iterate through the string with an index i:
- If the current character differs from the previous, push 1 onto the stack.
- If it matches, increment the top of the stack.
- If the count reaches k, pop from the stack, delete those k characters, and adjust the index.
Continue until the end of the string.
Return the resulting string.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []
        n = len(s)
        i = 0
        s = list(s)

        while i < n:
            if i == 0 or s[i] != s[i - 1]:
                stack.append(1)
            else:
                stack[-1] += 1
                if stack[-1] == k:
                    stack.pop()
                    del s[i - k + 1:i + 1]
                    i -= k
                    n -= k

            i += 1

        return ''.join(s)

public class Solution {
    public String removeDuplicates(String s, int k) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Integer> stack = new Stack<>();
        int i = 0;

        while (i < sb.length()) {
            if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) {
                stack.push(1);
            } else {
                stack.push(stack.pop() + 1);
                if (stack.peek() == k) {
                    stack.pop();
                    sb.delete(i - k + 1, i + 1);
                    i -= k;
                }
            }
            i++;
        }

        return sb.toString();
    }
}

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<int> stack;
        int n = s.length(), i = 0;

        while (i < n) {
            if (i == 0 || s[i] != s[i - 1]) {
                stack.push_back(1);
            } else {
                stack.back()++;
                if (stack.back() == k) {
                    stack.pop_back();
                    s.erase(i - k + 1, k);
                    i -= k;
                    n -= k;
                }
            }
            i++;
        }

        return s;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {string}
     */
    removeDuplicates(s, k) {
        let stack = [];
        let arr = s.split('');
        let i = 0;

        while (i < arr.length) {
            if (i === 0 || arr[i] !== arr[i - 1]) {
                stack.push(1);
            } else {
                stack[stack.length - 1]++;
                if (stack[stack.length - 1] === k) {
                    stack.pop();
                    arr.splice(i - k + 1, k);
                    i -= k;
                }
            }
            i++;
        }

        return arr.join('');
    }
}

public class Solution {
    public string RemoveDuplicates(string s, int k) {
        var stack = new List<int>();
        var chars = new List<char>(s);
        int n = chars.Count;
        int i = 0;

        while (i < n) {
            if (i == 0 || chars[i] != chars[i - 1]) {
                stack.Add(1);
            } else {
                stack[stack.Count - 1]++;
                if (stack[stack.Count - 1] == k) {
                    stack.RemoveAt(stack.Count - 1);
                    chars.RemoveRange(i - k + 1, k);
                    i -= k;
                    n -= k;
                }
            }
            i++;
        }

        return new string(chars.ToArray());
    }
}

func removeDuplicates(s string, k int) string {
    stack := []int{}
    arr := []byte(s)
    n := len(arr)
    i := 0

    for i < n {
        if i == 0 || arr[i] != arr[i-1] {
            stack = append(stack, 1)
        } else {
            stack[len(stack)-1]++
            if stack[len(stack)-1] == k {
                stack = stack[:len(stack)-1]
                arr = append(arr[:i-k+1], arr[i+1:]...)
                i -= k
                n -= k
            }
        }
        i++
    }

    return string(arr)
}

class Solution {
    fun removeDuplicates(s: String, k: Int): String {
        val stack = mutableListOf<Int>()
        val arr = StringBuilder(s)
        var n = arr.length
        var i = 0

        while (i < n) {
            if (i == 0 || arr[i] != arr[i - 1]) {
                stack.add(1)
            } else {
                stack[stack.size - 1]++
                if (stack[stack.size - 1] == k) {
                    stack.removeAt(stack.size - 1)
                    arr.delete(i - k + 1, i + 1)
                    i -= k
                    n -= k
                }
            }
            i++
        }

        return arr.toString()
    }
}

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        var stack = [Int]()
        var arr = Array(s)
        var n = arr.count
        var i = 0

        while i < n {
            if i == 0 || arr[i] != arr[i - 1] {
                stack.append(1)
            } else {
                stack[stack.count - 1] += 1
                if stack[stack.count - 1] == k {
                    stack.removeLast()
                    arr.removeSubrange((i - k + 1)...i)
                    i -= k
                    n -= k
                }
            }
            i += 1
        }

        return String(arr)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Stack (Optimal)

Intuition

Instead of modifying the string and tracking counts separately, we can store both the character and its count together in the stack. This eliminates the need for in-place string manipulation and index adjustments.

Each stack entry is a pair of (character, count). When we encounter a new character, we either increment the count of the top entry (if it matches) or push a new entry. When a count reaches k, we simply pop that entry. Building the result at the end involves expanding each entry back into its characters.

Algorithm

Initialize a stack where each entry stores a character and its consecutive count.
For each character in the string:
- If the stack is non-empty and the top character matches, increment its count.
- Otherwise, push a new entry with count 1.
- If the count reaches k, pop the entry from the stack.
Build the result by expanding each stack entry: repeat each character by its count.
Return the resulting string.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        stack = []  # [char, count]

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

        return ''.join(char * count for char, count in stack)

public class Solution {
    public String removeDuplicates(String s, int k) {
        Stack<int[]> stack = new Stack<>(); // [char, count]

        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek()[0] == c) {
                stack.peek()[1]++;
            } else {
                stack.push(new int[] {c, 1});
            }
            if (stack.peek()[1] == k) {
                stack.pop();
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            int[] top = stack.pop();
            res.append(String.valueOf((char) top[0]).repeat(top[1]));
        }

        return res.reverse().toString();
    }
}

class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> stack;

        for (char c : s) {
            if (!stack.empty() && stack.back().first == c) {
                stack.back().second++;
            } else {
                stack.push_back({c, 1});
            }
            if (stack.back().second == k) {
                stack.pop_back();
            }
        }

        string res;
        for (auto& p : stack) {
            res.append(p.second, p.first);
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {string}
     */
    removeDuplicates(s, k) {
        const stack = []; // [char, count]

        for (const c of s) {
            if (stack.length && stack[stack.length - 1][0] === c) {
                stack[stack.length - 1][1]++;
            } else {
                stack.push([c, 1]);
            }
            if (stack[stack.length - 1][1] === k) {
                stack.pop();
            }
        }

        let res = '';
        for (const [char, count] of stack) {
            res += char.repeat(count);
        }

        return res;
    }
}

public class Solution {
    public string RemoveDuplicates(string s, int k) {
        var stack = new List<(char ch, int cnt)>();

        foreach (char c in s) {
            if (stack.Count > 0 && stack[stack.Count - 1].ch == c) {
                var top = stack[stack.Count - 1];
                stack[stack.Count - 1] = (top.ch, top.cnt + 1);
            } else {
                stack.Add((c, 1));
            }

            if (stack[stack.Count - 1].cnt == k) {
                stack.RemoveAt(stack.Count - 1);
            }
        }

        var sb = new System.Text.StringBuilder();
        foreach (var (ch, cnt) in stack) {
            sb.Append(new string(ch, cnt));
        }

        return sb.ToString();
    }
}

func removeDuplicates(s string, k int) string {
    stack := [][]int{} // [char, count]

    for _, c := range s {
        if len(stack) > 0 && stack[len(stack)-1][0] == int(c) {
            stack[len(stack)-1][1]++
        } else {
            stack = append(stack, []int{int(c), 1})
        }
        if stack[len(stack)-1][1] == k {
            stack = stack[:len(stack)-1]
        }
    }

    var res strings.Builder
    for _, item := range stack {
        for i := 0; i < item[1]; i++ {
            res.WriteByte(byte(item[0]))
        }
    }

    return res.String()
}

class Solution {
    fun removeDuplicates(s: String, k: Int): String {
        val stack = mutableListOf<Pair<Char, Int>>()

        for (c in s) {
            if (stack.isNotEmpty() && stack.last().first == c) {
                stack[stack.size - 1] = c to stack.last().second + 1
            } else {
                stack.add(c to 1)
            }
            if (stack.last().second == k) {
                stack.removeLast()
            }
        }

        val res = StringBuilder()
        for ((ch, cnt) in stack) {
            res.append(ch.toString().repeat(cnt))
        }

        return res.toString()
    }
}

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        var stack = [(Character, Int)]()

        for c in s {
            if !stack.isEmpty && stack.last!.0 == c {
                stack[stack.count - 1].1 += 1
            } else {
                stack.append((c, 1))
            }
            if stack.last!.1 == k {
                stack.removeLast()
            }
        }

        var res = ""
        for (ch, cnt) in stack {
            res += String(repeating: String(ch), count: cnt)
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Two Pointers

Intuition

This approach uses the input array itself as both the working space and the result, avoiding the need for a separate stack data structure. We use two pointers: j reads through the original string while i writes the result.

A separate count array tracks consecutive occurrences at each write position. When we write a character, we check if it matches the previous written character to determine its count. If the count reaches k, we "rewind" the write pointer by k positions, effectively removing those characters.

Algorithm

Convert the string to a mutable character array and create a count array of the same size.
Use two pointers: j iterates through the original string, i tracks the write position.
For each character at position j:
- Copy it to position i.
- Set its count to 1. If the previous character (at i-1) is the same, add the previous count to the current count.
- If the count reaches k, move i back by k positions.
- Increment i.
Return the substring from 0 to i.

class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        i = 0
        n = len(s)
        count = [0] * n
        s = list(s)
        for j in range(n):
            s[i] = s[j]
            count[i] = 1
            if i > 0 and s[i - 1] == s[j]:
                count[i] += count[i - 1]
            if count[i] == k:
                i -= k
            i += 1
        return ''.join(s[:i])

public class Solution {
    public String removeDuplicates(String s, int k) {
        int i = 0, n = s.length();
        char[] str = s.toCharArray();
        int[] count = new int[n];
        for (int j = 0; j < n; j++) {
            str[i] = str[j];
            count[i] = 1;
            if (i > 0 && str[i - 1] == str[j]) {
                count[i] += count[i - 1];
            }
            if (count[i] == k) {
                i -= k;
            }
            i++;
        }
        return new String(str, 0, i);
    }
}

class Solution {
public:
    string removeDuplicates(string s, int k) {
        int i = 0, n = s.length();
        vector<int> count(n);
        for (int j = 0; j < n; i++, j++) {
            s[i] = s[j];
            count[i] = 1;
            if (i > 0 && s[i - 1] == s[j]) {
                count[i] += count[i - 1];
            }
            if (count[i] == k) i -= k;
        }
        return s.substr(0, i);
    }
};

class Solution {
    /**
     * @param {string} s
     * @param {number} k
     * @return {string}
     */
    removeDuplicates(s, k) {
        let i = 0;
        const n = s.length;
        const count = new Array(n).fill(0);
        s = s.split('');
        for (let j = 0; j < n; j++) {
            s[i] = s[j];
            count[i] = 1;
            if (i > 0 && s[i - 1] === s[j]) {
                count[i] += count[i - 1];
            }
            if (count[i] === k) {
                i -= k;
            }
            i++;
        }
        return s.slice(0, i).join('');
    }
}

public class Solution {
    public string RemoveDuplicates(string s, int k) {
        int n = s.Length;
        char[] arr = s.ToCharArray();
        int[] count = new int[n];
        int i = 0;

        for (int j = 0; j < n; j++) {
            arr[i] = arr[j];
            count[i] = 1;

            if (i > 0 && arr[i - 1] == arr[j]) {
                count[i] += count[i - 1];
            }

            if (count[i] == k) {
                i -= k;
            }

            i++;
        }

        return new string(arr, 0, i);
    }
}

func removeDuplicates(s string, k int) string {
    n := len(s)
    arr := []byte(s)
    count := make([]int, n)
    i := 0

    for j := 0; j < n; j++ {
        arr[i] = arr[j]
        count[i] = 1
        if i > 0 && arr[i-1] == arr[j] {
            count[i] += count[i-1]
        }
        if count[i] == k {
            i -= k
        }
        i++
    }

    return string(arr[:i])
}

class Solution {
    fun removeDuplicates(s: String, k: Int): String {
        val n = s.length
        val arr = s.toCharArray()
        val count = IntArray(n)
        var i = 0

        for (j in 0 until n) {
            arr[i] = arr[j]
            count[i] = 1
            if (i > 0 && arr[i - 1] == arr[j]) {
                count[i] += count[i - 1]
            }
            if (count[i] == k) {
                i -= k
            }
            i++
        }

        return String(arr, 0, i)
    }
}

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        let n = s.count
        var arr = Array(s)
        var count = [Int](repeating: 0, count: n)
        var i = 0

        for j in 0..<n {
            arr[i] = arr[j]
            count[i] = 1
            if i > 0 && arr[i - 1] == arr[j] {
                count[i] += count[i - 1]
            }
            if count[i] == k {
                i -= k
            }
            i += 1
        }

        return String(arr.prefix(i))
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Not Continuing After Removal Creates New Groups

After removing k adjacent duplicates, the characters before and after the removed section may now be adjacent and form a new group of duplicates. A common mistake is stopping after a single removal pass. The solution must continue checking for new groups that may have been created by previous removals.

Resetting Count When Characters Match After Removal

When using a stack-based approach, after removing k characters, the new top of the string may match the next character being processed. Failing to properly inherit or restore the count from before the removal leads to incorrect duplicate detection. The count must reflect the consecutive sequence that existed before the removal.

Off-by-One Errors in Substring Removal

When removing k characters ending at index i, the removal range is from i - k + 1 to i (inclusive). A common bug is using i - k as the start index or forgetting to adjust the current index after removal. Both the string length and the iteration index must be updated correctly to avoid processing removed characters or skipping valid ones.