Remove All Adjacent Duplicates in String II

Medium
404.

Remove All Adjacent Duplicates in String II

Remove All Adjacent Duplicates in String II is a medium coding problem on strings and stack, asked in Amazon, Google and Bloomberg interviews.

You are given a string s and an integer k. A k-duplicate removal deletes k adjacent and equal characters from s, joining what is left.

Repeat the removal until it is no longer possible and return the final string. The answer is unique.

Example 1

Input
s = "abcd", k = 2
Output
abcd
Explanation
Nothing to remove.

Example 2

Input
s = "deeedbbcccbdaa", k = 3
Output
aa

Example 3

Input
s = "pbbcggttciiippooaais", k = 2
Output
ps

Constraints

  • 1 <= s.length <= 40
  • 2 <= k <= 6
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
var removeDuplicates = function(s, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Remove All Adjacent Duplicates in String II — Solution

Remove All Adjacent Duplicates in String II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Remove All Adjacent Duplicates in String II is a medium coding problem on strings and stack, asked in Amazon, Google and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Strings, Stack
  • Asked at: Amazon, Google, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s and an integer k. A k-duplicate removal deletes k adjacent and equal characters from s, joining what is left.

Repeat the removal until it is no longer possible and return the final string. The answer is unique.

Example 1

Input: s = "abcd", k = 2
Output: abcd
Explanation: Nothing to remove.

Example 2

Input: s = "deeedbbcccbdaa", k = 3
Output: aa

Example 3

Input: s = "pbbcggttciiippooaais", k = 2
Output: ps

Constraints

  • 1 <= s.length <= 40
  • 2 <= k <= 6
  • s consists of lowercase English letters.

Hints for Remove All Adjacent Duplicates in String II

  1. Hint 1

    Deleting characters can make new runs adjacent, so a single scan with a stack is the clean approach.

  2. Hint 2

    Store pairs of (character, run length) on the stack instead of individual characters.

  3. Hint 3

    When a run length hits k, pop the whole frame — the frames below then become adjacent automatically.

How to solve Remove All Adjacent Duplicates in String II

Stack of (character, run length) frames; extend the top when the character matches, pop the frame when its length reaches k.

Approach

  1. For each ch: increment the top's count if it matches, else push [ch, 1].
  2. If the top's count equals k, pop it.
  3. Expand the frames into the answer.

Why it works

Removing a run can join the runs on either side, and the frame stack keeps the left neighbour on top so the join is detected on the next character.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Storing individual characters instead of counts makes the k-check O(k) each time.

Reference solution

Python

def removeDuplicates(s: str, k: int) -> str:
    stack = []
    for ch in s:
        if stack and stack[-1][0] == ch:
            stack[-1][1] += 1
        else:
            stack.append([ch, 1])
        if stack[-1][1] == k:
            stack.pop()
    return "".join(ch * count for ch, count in stack)

Java

public static String removeDuplicates(String s, int k) {
    List<Character> chars = new ArrayList<>();
    List<Integer> counts = new ArrayList<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (!chars.isEmpty() && chars.get(chars.size() - 1) == c) {
            counts.set(counts.size() - 1, counts.get(counts.size() - 1) + 1);
        } else {
            chars.add(c);
            counts.add(1);
        }
        if (counts.get(counts.size() - 1) == k) {
            chars.remove(chars.size() - 1);
            counts.remove(counts.size() - 1);
        }
    }
    StringBuilder out = new StringBuilder();
    for (int i = 0; i < chars.size(); i++) {
        for (int j = 0; j < counts.get(i); j++) out.append(chars.get(i));
    }
    return out.toString();
}

C++

string removeDuplicates(string s, int k) {
    vector<char> chars;
    vector<int> counts;
    for (char c : s) {
        if (!chars.empty() && chars.back() == c) {
            counts.back()++;
        } else {
            chars.push_back(c);
            counts.push_back(1);
        }
        if (counts.back() == k) {
            chars.pop_back();
            counts.pop_back();
        }
    }
    string out;
    for (size_t i = 0; i < chars.size(); i++) {
        out.append((size_t) counts[i], chars[i]);
    }
    return out;
}

JavaScript

var removeDuplicates = function(s, k) {
    const chars = [], counts = [];
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if (chars.length > 0 && chars[chars.length - 1] === c) {
            counts[counts.length - 1]++;
        } else {
            chars.push(c);
            counts.push(1);
        }
        if (counts[counts.length - 1] === k) {
            chars.pop();
            counts.pop();
        }
    }
    let out = "";
    for (let i = 0; i < chars.length; i++) {
        for (let j = 0; j < counts[i]; j++) out += chars[i];
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure