Given a string s, 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 <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: class Solution:
    def removeDuplicates(self, s: str, k: int) -> str:
        

Solutions:
class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		st = [['*', 0]]
		for c in s:
			if c != st[-1][0]:
				st.append([c, 1])
			else:
				st[-1][1] += 1
				if st[-1][1] == k:
					st.pop()
		res = ''
		for (c, v) in st:
			res += c * v
		return res


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		if not s or k == 0:
			return s
		stack = [['#', 0]]
		for c in s:
			if stack[-1][0] == c:
				stack[-1][1] += 1
				if stack[-1][1] == k:
					stack.pop()
			else:
				stack.append([c, 1])
		return ''.join((c * k for (c, k) in stack))


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		res = []
		char = s[0]
		count = 1
		for i in range(1, len(s)):
			if s[i] == char:
				count += 1
			else:
				count = 1
				char = s[i]
			if count == k:
				return self.removeDuplicates(s[:i - k + 1] + s[i + 1:], k)
		return s


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		if len(s) < k:
			return s
		stack = [[0, '#']]
		for char in s:
			if char == stack[-1][1]:
				stack[-1][0] += 1
				if stack[-1][0] == k:
					stack.pop()
			else:
				stack.append([1, char])
		return ''.join((c * k for (c, k) in stack))


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		unique = set(s)
		dups = []
		for c in unique:
			dups.append(c * k)
		while True:
			start = s
			for c in dups:
				s = s.replace(c, '')
			if start == s:
				return s


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		lengths = [[None, 0]]
		idx = 0
		while idx < len(s):
			current = lengths[-1][0]
			if current == s[idx]:
				lengths[-1][1] += 1
			else:
				lengths.append([s[idx], 1])
				current = s[idx]
			if lengths[-1][1] == k:
				lengths.pop()
				s = s[:idx - k + 1] + s[idx + 1:]
				idx -= k
			idx += 1
		return s


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		ret = list(s)
		while True:
			s = ret
			ret = []
			ac = 1
			for c in s:
				if not ret or ret[-1] != c:
					ac = 1
					ret.append(c)
				elif ac + 1 == k:
					while ac:
						ret.pop()
						ac -= 1
				else:
					ret.append(c)
					ac += 1
			if len(ret) == len(s):
				break
		return ''.join(ret)


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		count = 1
		flag = 1
		last_idx = 0
		while 1:
			i = 0
			temp_s = s
			while i < len(s) - 1:
				if s[i] != s[i + 1]:
					i = i + 1
				else:
					last_idx = i
					while 1:
						if i + 1 == len(s):
							break
						elif s[i] == s[i + 1]:
							count = count + 1
							i = i + 1
						else:
							break
					if count >= k:
						s = s[:last_idx] + s[last_idx + k:]
						i = last_idx
					count = 1
			if temp_s == s:
				break
		return s


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		while True:
			stk = []
			s_new = []
			for c in s:
				if len(stk) == k:
					stk = []
				while stk and c != stk[-1]:
					s_new.append(stk.pop())
				stk.append(c)
				if len(stk) == k:
					stk = []
			while stk:
				s_new.append(stk.pop())
			print(''.join(s_new))
			if s == s_new:
				break
			s = s_new
		return ''.join(s)


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		ns = []
		deleted = True
		while deleted:
			deleted = False
			i = 0
			ns = []
			while i < len(s):
				if i <= len(s) - k and s[i + 1:i + k] == s[i] * (k - 1):
					deleted = True
					i += k
				else:
					ns.append(s[i])
					i += 1
			s = ''.join(ns)
		return s


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:

		def helper(s):
			ans = []
			i = 0
			while i < len(s):
				if s[i] * k != s[i:i + k]:
					ans.append(s[i])
					i += 1
				else:
					i += k
			if len(ans) == len(s):
				res.append(''.join(ans))
				return
			else:
				helper(''.join(ans))
		res = []
		helper(s)
		return res[0]


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		sliced = True
		while sliced == True:
			(s, sliced) = self.getSlices(s, k)
		return s

	def getSlices(self, s, k):
		sliced = False
		idx = set()
		i = 0
		while i < len(s):
			if s[i] * k == s[i:i + k]:
				idx.update(range(i, i + k))
				sliced = True
				i += k
			i += 1
		if sliced:
			new_str = ''.join([char for (i, char) in enumerate(s) if i not in idx])
			return (new_str, sliced)
		return (s, sliced)


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		len_s = len(s)
		if k > len_s:
			return s

		def helper(string, itr_range):
			not_found = False
			while not not_found:
				not_found = True
				for i in range(itr_range):
					if string[i:i + k] == string[i] * k:
						string = string[:i] + string[i + k:]
						itr_range = len(string) - k + 1
						not_found = False
						break
			return string
		return helper(s, len_s - k + 1)


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		if len(s) < k:
			return s
		found = self.findStr(s, k)
		if not found:
			return s
		else:
			return self.removeDuplicates(s.replace(found, ''), k)

	def findStr(self, s: str, k: int):
		for i in range(len(s)):
			if s[i] * k in s:
				return s[i] * k
		return None


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		distinct = len(set(s))
		while len(s) >= k:
			new_s = ''
			(cur, count) = (s[0], 1)
			for i in range(1, len(s)):
				print(cur, count)
				if s[i] == cur:
					count += 1
				else:
					new_s += cur * (count % k)
					(cur, count) = (s[i], 1)
			new_s += cur * (count % k)
			if s == new_s:
				break
			s = new_s
		return s


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		duplicates = [k * i for i in 'abcdefghijklmnopqrstuvwxyz']
		counter = 0
		while counter != len(s):
			counter = len(s)
			for i in duplicates:
				s = s.replace(i, '')
		return s


class Solution:

	def removeDuplicates(self, s: str, k: int) -> str:
		if not s:
			return ''
		stack = []
		prev = count = None
		for i in range(0, len(s)):
			if not prev:
				(prev, count) = (s[i], 1)
			elif s[i] == prev:
				count += 1
			else:
				stack.append((prev, count))
				prev = s[i]
				count = 1
			if count == k:
				if stack:
					(prev, count) = stack.pop()
				else:
					prev = None
		stack.append((prev, count))
		output = ''
		for (e, c) in stack:
			output += e * c
		return output