Remove-all-adjacent-duplicates-in-string-ii Solution

Tags: leetcode stack python java scala javascript

Problem Statement

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¹.

  All my solutions are uploaded to Github repository

Testcase

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 <= 105
• 2 <= k <= 104
• s only contains lower case English letters.

Explanation

1. Use a stack and store a pair of character and its count.
2. Update the count of character if its adjacent.
3. If the count equals to the value of k then remove the character.
4. Iterate over the stack to generate the output string.

For example for Input: s = "deeedbbcccbdaa", k = 3.

Solution

• Java
• Python
• Javascript
• Scala

	class Node {
	private char key;
	private int value;
	public Node(char key, int value) {
	this.key = key;
	this.value = value;
	}
	public char getKey() {
	return key;
	}
	public int getValue() {
	return value;
	}
	}
	class Solution {
	public String removeDuplicates(String s, int k) {
	if (s.isEmpty() || s.length() < k){
	return s;
	}
	Deque<Node> stack = new ArrayDeque<>();
	for (char c : s.toCharArray()){
	if (stack.isEmpty()) {
	stack.push(new Node(c, 1));
	} else {
	if (stack.peek().getKey() == c){
	Node temp = stack.pop();
	stack.push(new Node(c, temp.getValue() + 1));
	} else {
	stack.push(new Node(c, 1));
	}
	}
	if (stack.peek().getValue() == k) {
	stack.pop();
	}
	}
	StringBuilder sb = new StringBuilder();
	for (Node node : stack){
	for (int i = 0; i < node.getValue(); i++){
	sb.append(node.getKey());
	}
	}
	return sb.reverse().toString();
	}
	}

view raw RemoveDuplicates.java hosted with ❤ by GitHub

	from dataclasses import dataclass
	from collections import deque
	@dataclass
	class Node:
	key : str
	value : int
	class Solution:
	def removeDuplicates(self, s: str, k: int) -> str:
	if not s or len(s) < k:
	return s
	stack = deque()
	for c in s:
	if len(stack) == 0:
	stack.append(Node(c, 1))
	else:
	if stack[-1].key == c:
	node = stack.pop()
	stack.append(Node(c, node.value + 1))
	else:
	stack.append(Node(c, 1))
	if stack[-1].value == k:
	stack.pop()
	output = ""
	for st in stack:
	count = st.value
	while count > 0:
	output = output + st.key
	count -= 1
	return output

view raw remove_duplicates.py hosted with ❤ by GitHub

	class Node {
	constructor(key, value){
	this._key = key;
	this._value = value;
	}
	get key() {
	return this._key;
	}
	get value() {
	return this._value;
	}
	}
	/**
	* @param {string} s
	* @param {number} k
	* @return {string}
	*/
	var removeDuplicates = function(s, k) {
	if(s.length === 0 || s.length < k){
	return s;
	}
	let stack = []
	for (let c of s) {
	if (stack.length === 0) {
	stack.push(new Node(c, 1))
	} else {
	if (stack[stack.length - 1].key == c){
	let node = stack.pop()
	stack.push(new Node(c, node.value + 1))
	} else {
	stack.push(new Node(c, 1))
	}
	}
	if (stack[stack.length - 1].value === k){
	stack.pop()
	}
	}
	let output = ""
	for (let st of stack){
	let count = st.value
	while (count-- > 0){
	output = output + st.key
	}
	}
	return output;
	};

view raw removeDuplicates.js hosted with ❤ by GitHub

	import scala.collection.mutable.Stack
	case class Node(key : Char, value : Int)
	object Solution {
	def removeDuplicates(s : String, k : Int) : String = {
	if ("".equals(s) || s.length < k){
	s
	} else {
	var stack = Stack[Node]()
	s.map( c=> {
	if (stack.isEmpty) {
	stack.push(Node(c, 1))
	} else {
	if (stack.top.key == c){
	var node = stack.pop()
	stack.push(Node(c, 1 + node.value))
	} else {
	stack.push(Node(c, 1))
	}
	}
	if (stack.top.value == k){
	stack.pop()
	}
	})
	var output = ""
	stack.map(st => {
	output = (st.key.toString * st.value) + output
	})
	output
	}
	}
	}

view raw RemoveDuplicates.scala hosted with ❤ by GitHub

Complexity

Time Complexity: O(N).

Space Complexity: O(N).

Footnotes

---

1. Remove All Adjacent Duplicates in String II

   ↩

---