Given a string s and an integer k, the task is to reduce the string by applying the following operation:
Choose a group of k consecutive identical characters and remove them.
The operation can be performed any number of times until it is no longer possible.
Example 1:
Input:
k = 2
s = "geeksforgeeks"
Output:
gksforgks
Explanation:
Modified String after each step: 
"geeksforgeeks" -> "gksforgks"
Example 2:
Input:
k = 2
s = "geegsforgeeeks" 
Output:
sforgeks
Explanation:
Modified String after each step:
"geegsforgeeeks" -> "ggsforgeks" -> "sforgeks"
Your Task:  
You don't need to read input or print anything. Complete the function Reduced_String() which takes integer k and string s as input parameters and returns the reduced string.
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(|s|)
Constraints:
1 ≤ |s| ≤ 10^{5}
1 ≤ k ≤ |s|

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(|s|)

Starter code:
#User function Template for python3



class Solution:

    def Reduced_String(self, k, s):

        # Your code goes here

        # return the reduced string



Solutions:
class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		count = 1
		stack = ['A']
		for elm in s:
			if stack == [0] or stack[-1] != elm:
				stack.append(elm)
			else:
				i = -1
				while stack[i] == elm and count < k:
					count += 1
					i -= 1
				if count == k:
					while count > 1:
						stack.pop()
						count -= 1
				else:
					stack.append(elm)
					count = 1
		return ''.join(stack)[1:]


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = []
		n = len(s)
		i = 0
		x = 0
		while i < n:
			if len(stack) > 0 and stack[-1][0] == s[i]:
				stack[-1][1] += 1
				if stack[-1][1] == k:
					stack.pop()
				i += 1
			else:
				x = 1
				stack.append([s[i], x])
				i += 1
		ans = ''
		for i in stack:
			for j in range(i[1]):
				ans += i[0]
		return ans


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		st = [-1]
		for ele in s:
			if ele != st[-1]:
				st.append(ele)
			else:
				j = len(st) - 1
				count = 1
				while st[j] != -1 and st[j] == ele:
					count += 1
					j -= 1
				if count == k:
					for i in range(k - 1):
						st.pop()
				else:
					st.append(ele)
		return ''.join(st[1:])


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = []
		for i in s:
			if len(stack) != 0 and stack[-1][0] == i:
				stack[-1][1] += 1
				if stack[-1][1] == k:
					stack.pop()
			else:
				stack.append([i, 1])
		res = ''
		for i in stack:
			for j in range(i[1]):
				res += i[0]
		return res


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		st = []
		n = len(s)
		(i, j) = (0, 0)
		while i < n:
			if len(st) > 0 and st[-1][0] == s[i]:
				st[-1][1] += 1
				if st[-1][1] == k:
					st.pop()
				i += 1
			else:
				j = 1
				st.append([s[i], j])
				i += 1
		res = ''
		for i in st:
			for j in range(i[1]):
				res += i[0]
		return res


class Solution:

	def Reduced_String(self, k, s):
		l = []
		for i in s:
			l.append(i)
			x = 0
			if len(l) >= k:
				for j in range(k, 0, -1):
					if l[-j] == i:
						x = x + 1
					else:
						pass
						break
			if x == k:
				for _ in range(k):
					l.pop()
		return ''.join(l)


class Solution:

	def Reduced_String(self, k, s):
		stack = list()
		crush = False
		for char in s:
			stack.append(char)
			if len(stack) >= k:
				for position in range(1, k + 1):
					if stack[-position] == char:
						crush = True
					else:
						crush = False
						break
			if crush:
				for _ in range(k):
					stack.pop()
				crush = False
		return ''.join(stack)


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		top = -1
		stack = []
		for char in s:
			if top == -1:
				stack.append([char, 1])
				top += 1
			elif stack[-1][0] == char:
				stack[-1][1] += 1
				if stack[-1][1] == k:
					stack.pop(-1)
					top -= 1
			else:
				stack.append([char, 1])
				top += 1
		final = ''
		for i in range(0, top + 1):
			(V, c) = stack[i]
			final += V * c
		return final


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		st = []
		for i in range(len(s)):
			if len(st) == 0:
				st.append([s[i], 1])
				continue
			if st[-1][0] == s[i]:
				pair = st.pop()
				pair[1] += 1
				if pair[1] == k:
					continue
				else:
					st.append(pair)
			else:
				st.append([s[i], 1])
		ans = ''
		for i in st:
			ans += i[0] * i[1]
		return ans


class Solution:

	def Reduced_String(self, k, s):
		while True:
			count = 0
			chars = set(s)
			for c in chars:
				if c * k in s:
					s = s.replace(c * k, '')
					count += 1
			if count == 0:
				break
		return s


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = []
		for c in s:
			if stack and stack[-1][0] == c:
				stack[-1][1] += 1
				if stack[-1][1] == k:
					stack.pop()
			else:
				stack.append([c, 1])
		return ''.join((c * count for (c, count) in stack))


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		crush = False
		for char in s:
			stack.append(char)
			if len(stack) >= k:
				for j in range(1, k + 1):
					if stack[-j] == char:
						crush = True
					else:
						crush = False
						break
			if crush:
				for i in range(k):
					stack.pop()
					crush = False
		return ''.join(stack)


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		res = ''
		count = 0
		i = 0
		if k < 2:
			return ''
		for char in s:
			if len(stack) == 0:
				stack.append((char, 1))
			elif stack[-1][0] != char:
				stack.append((char, 1))
			elif stack[-1][0] == char:
				count = stack[-1][1] + 1
				if count == k:
					while stack and stack[-1][0] == char:
						stack.pop()
				else:
					stack.append((char, count))
		for i in range(len(stack)):
			res += stack[i][0]
		return res


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		count = 0
		if k < 2:
			return ''
		for char in s:
			if not stack:
				stack.append((char, 1))
			elif stack[-1][0] != char:
				stack.append((char, 1))
			elif stack[-1][0] == char:
				count = stack[-1][1] + 1
				if count == k:
					while stack and char == stack[-1][0]:
						stack.pop()
				else:
					stack.append((char, count))
		res = ''
		for ele in stack:
			res += ele[0]
		return res


class Solution:

	def Reduced_String(self, k, s):
		stk = []
		i = 0
		cnt = 1
		ans = ''
		if k == 1:
			return ans
		while i < len(s):
			if len(stk) != 0:
				if s[i] != stk[-1]:
					stk.append(s[i])
					cnt = 1
				else:
					cnt += 1
					if cnt == k:
						j = 1
						while j < k:
							stk.pop()
							j += 1
						l = len(stk) - 2
						cnt = 1
						while l >= 0:
							if stk[l] == stk[-1]:
								cnt += 1
							else:
								break
							l -= 1
					else:
						stk.append(s[i])
			else:
				stk.append(s[i])
				cnt = 1
			i += 1
		for i in stk:
			ans += i
		return ans


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		count = 1
		stk = ['A']
		for e in s:
			if stk == 0 or stk[-1] != e:
				stk.append(e)
			elif stk[-1] == e:
				i = -1
				while stk[i] == e and count < k:
					count += 1
					i -= 1
				if count == k:
					while count > 1:
						stk.pop()
						count -= 1
				else:
					stk.append(e)
					count = 1
		return ''.join(stk)[1:]


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		count = 1
		stk = ['A']
		for ch in s:
			if stk == [0] or stk[-1] != ch:
				stk.append(ch)
			else:
				i = -1
				while stk[i] == ch and count < k:
					count += 1
					i -= 1
				if count == k:
					while count > 1:
						stk.pop()
						count -= 1
				else:
					stk.append(ch)
					count = 1
		return ''.join(stk)[1:]
		ans = ''
		for i in st:
			ans = ans + i
		return ans


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		st = []
		c = 1
		for i in s:
			if len(st) == 0:
				st.append(i)
			elif st[-1] == i:
				j = -1
				while c < k and j != -1 * len(st) - 1:
					if st[j] == i:
						c += 1
					else:
						break
					j -= 1
				if c == k:
					while c != 1:
						st.pop()
						c -= 1
				else:
					c = 1
					st.append(i)
			else:
				c = 1
				st.append(i)
		ns = ''
		for i in st:
			ns = ns + i
		return ns


class Solution:

	def Reduced_String(self, k, s):
		li = []
		func = False
		for i in range(len(s)):
			li.append(s[i])
			if len(li) >= k:
				for j in range(1, k + 1):
					if li[-j] == s[i]:
						func = True
					else:
						func = False
						break
			if func:
				for j in range(k):
					li.pop()
				func = False
		res = ''.join(li)
		return res


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		if k == 1:
			return ''
		for i in s:
			if not stack or stack[-1][0] != i:
				stack.append((i, 1))
			elif stack[-1][0] == i and stack[-1][1] != k - 1:
				stack.append((i, stack[-1][1] + 1))
			elif stack[-1][0] == i and stack[-1][1] == k - 1:
				for j in range(k - 1):
					stack.pop()
		res = ''
		while stack:
			res += stack[-1][0]
			stack.pop()
		return res[::-1]


class Solution:

	def Reduced_String(self, k, st):
		s = []
		n = len(st)
		ans = ''
		if k == 1:
			return ''
		for i in range(n):
			if not s or (s and st[i] != s[-1][0]):
				s.append((st[i], 1))
			elif s[-1][0] == st[i] and s[-1][1] != k - 1:
				s.append((st[i], s[-1][1] + 1))
			elif s[-1][0] == st[i] and s[-1][1] == k - 1:
				for i in range(k - 1):
					s.pop()
		while s:
			ans += s[-1][0]
			s.pop()
		ans1 = ans[::-1]
		return ans1


class Solution:

	def Reduced_String(self, k, s):
		st = []
		p = ''
		if k == 1:
			return ''
		for i in range(len(s)):
			if not st:
				st.append((s[i], 1))
				continue
			if st[-1][0] == s[i]:
				l = st.pop()
				l = (l[0], l[1] + 1)
				if l[1] == k:
					continue
				else:
					st.append(l)
			else:
				st.append((s[i], 1))
		temp = ''
		while st:
			cnt = st[-1][1]
			while cnt > 0:
				temp += st[-1][0]
				cnt -= 1
			st.pop()
		return temp[::-1]


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		st = []
		count = 1
		for ele in s:
			if st == []:
				st.append((ele, 1))
			elif ele == st[-1][0]:
				count = st[-1][1] + 1
				if count == k:
					while st and ele == st[-1][0]:
						st.pop()
				else:
					st.append((ele, count))
			else:
				st.append((ele, 1))
		res = ''
		for ele in st:
			res += ele[0]
		return res


class Solution:

	def Reduced_String(self, k, s):
		d = ''
		if k == 1:
			return d
		else:
			stack = []
			for i in s:
				d += i
				if stack:
					if stack[-1][0] == i:
						stack[-1][1] += 1
						if stack[-1][1] == k:
							d = d[0:len(d) - k]
							stack.pop()
					else:
						stack.append([i, 1])
				else:
					stack.append([i, 1])
			return d


from collections import defaultdict

class Solution:

	def Reduced_String(self, k, s):
		flag = False
		stk = []
		for i in s:
			stk.append(i)
			if len(stk) >= k:
				for p in range(1, k + 1):
					if stk[-p] == i:
						flag = True
					else:
						flag = False
						break
			if flag:
				for j in range(k):
					stk.pop()
				flag = False
		return ''.join(stk)


from collections import deque

class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			ret = ''
			return ret
		q = deque()
		for c in s:
			if len(q) and q[-1][0] == c:
				q[-1][1] += 1
				if q[-1][1] == k:
					q.pop()
			else:
				q.append([c, 1])
		ret = ''
		while len(q):
			ret += q[0][0] * q[0][1]
			q.popleft()
		return ret


def push(val, st, remainder):
	if remainder != 0:
		st.append([val, remainder])
	return

class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		st = []
		n = len(s)
		i = 0
		while i < n:
			count = 1
			while i < n - 1 and s[i] == s[i + 1]:
				count += 1
				i += 1
			remainder = count % k
			push(s[i], st, remainder)
			if len(st) > 1 and st[-1][0] == st[-2][0]:
				v1 = st.pop()
				v2 = st.pop()
				sumis = v1[1] + v2[1]
				remainder = sumis % k
				push(v1[0], st, remainder)
			i += 1
		ans = ''
		for val in st:
			ans += val[0] * val[1]
		return ans


from collections import deque

class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = deque()
		for i in range(len(s)):
			if len(stack) > 0 and stack[-1][0] == s[i]:
				stack[-1][1] += 1
				if stack[-1][1] == k:
					stack.pop()
			else:
				stack.append([s[i], 1])
		reduced_string = ''
		while stack:
			(char, count) = stack.popleft()
			reduced_string += char * count
		return reduced_string


from collections import deque

class Solution:

	def Reduced_String(self, k, s):
		stack = deque()
		for character in s:
			count = (0 if len(stack) == 0 or stack[-1][0] != character else stack[-1][1]) + 1
			if count == k:
				for i in range(k - 1):
					stack.pop()
			else:
				stack.append((character, count))
		res = ''.join(map(lambda x: x[0], stack))
		return res


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		for l in s:
			if stack and l == stack[-1][0]:
				stack[-1][1] += 1
			else:
				stack.append([l, 1])
			if stack[-1][1] == k:
				stack.pop(-1)
		S = ''
		for entry in stack:
			for i in range(entry[1]):
				S += entry[0]
		return S


from collections import deque

class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		items = deque()
		freq = deque()
		for item in s:
			if not items:
				items.append(item)
				freq.append(1)
			elif item != items[-1]:
				items.append(item)
				freq.append(1)
			elif freq[-1] == k - 1:
				freq.pop()
				items.pop()
			else:
				freq.append(freq.pop() + 1)
		result = ''
		for item in items:
			result += item * freq.popleft()
		return result


class Solution:

	def Reduced_String(self, k, s):
		st = []
		curr = 0
		if k <= 1:
			return ''
		for i in s:
			if len(st) == 0 or st[-1] != i:
				st.append(i)
				curr = 1
			else:
				st.append(i)
				curr += 1
				if curr == k:
					for j in range(k):
						st.pop()
				curr = 0
				if len(st) > 0:
					curr = 1
					for j in range(len(st) - 2, -1, -1):
						if st[j] == st[j + 1]:
							curr += 1
						else:
							break
		return ''.join(st)


class Solution:

	def Reduced_String(self, k, s):
		can_be_reduced = True
		while can_be_reduced:
			can_be_reduced = False
			cset = set(s)
			for char in cset:
				if char * k in s:
					s = s.replace(char * k, '')
					can_be_reduced = True
		return s


class Solution:

	def Reduced_String(self, k, s):
		if k <= 1:
			return ''
		dp = [[s[0], 1]]
		for i in range(1, len(s)):
			if len(dp) == 0:
				dp.append([s[i], 1])
			elif dp[-1][0] == s[i]:
				dp[-1][1] += 1
			else:
				dp.append([s[i], 1])
			if dp[-1][1] == k:
				dp.pop()
		res = ''
		for i in dp:
			for j in range(i[1]):
				res += i[0]
		return res


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = []
		n = len(s)
		for i in range(n):
			ch = s[i]
			if not stack:
				stack.append([ch, 1])
			elif stack[-1][0] == ch:
				(top_ch, top_freq) = stack[-1]
				top_freq += 1
				stack.append([ch, top_freq])
				if top_freq == k:
					for _ in range(k):
						stack.pop()
			else:
				stack.append([ch, 1])
		res = ''
		while stack:
			(ch, _) = stack.pop()
			res += ch
		res = res[::-1]
		return res


class Solution:

	def popKEquals(self, stack, k):
		if len(stack) == 0:
			return False
		c = []
		c.append(stack.pop())
		ctr = 1
		if k == 1:
			while len(stack) > 0:
				stack.pop()
			return True
		while ctr < k:
			if len(stack) > 0:
				if stack[-1] != c[-1] and ctr < k:
					while len(c) > 0:
						stack.append(c.pop())
					return False
				ctr += 1
				c.append(stack.pop())
			else:
				while len(c) > 0:
					stack.append(c.pop())
				return False
		return True

	def Reduced_String(self, k, s):
		st = []
		for i in s:
			st.append(i)
			self.popKEquals(st, k)
		return ''.join(st)


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = []
		for c in s:
			add_to_stack(stack, c, k)
		return ''.join([''.join([c] * r) for (c, r) in stack])

def add_to_stack(stack, c, k):
	if len(stack) == 0:
		stack.append([c, 1])
	elif stack[-1][0] == c:
		stack[-1][1] += 1
		if stack[-1][1] == k:
			stack.pop(-1)
	elif stack[-1][0] != c:
		stack.append([c, 1])


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		l = -1
		stack = []
		for i in range(len(s)):
			if not stack:
				stack.append((s[i], 1))
			elif stack[-1][0] == s[i]:
				if stack[-1][1] + 1 == k:
					for j in range(k - 1):
						if stack:
							stack.pop()
				else:
					stack.append((s[i], stack[-1][1] + 1))
			elif stack[-1][0] != s[i]:
				stack.append((s[i], 1))
		ans = ''
		for i in range(len(stack)):
			ans += stack[i][0]
		return ans


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		for char in s:
			if len(stack) == 0 or stack[-1][0] != char:
				stack.append([char, 1])
			elif len(stack) > 0 and stack[-1][0] == char:
				stack.append([char, stack[-1][1] + 1])
			if len(stack) > 0 and stack[-1][1] == k:
				for _ in range(k):
					stack.pop()
		ans = ''
		for element in stack:
			ans += element[0]
		return ans


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack_1 = []
		for i in s:
			if len(stack_1) == 0 or stack_1[-1][0] != i:
				stack_1.append([i, 1])
			elif stack_1[-1][0] == i:
				freq = stack_1[-1][1] + 1
				stack_1.pop()
				if freq < k:
					stack_1.append([i, freq])
		ans1 = ''
		for i in range(len(stack_1)):
			char_var = stack_1[i][0]
			freq = stack_1[i][1]
			while freq > 0:
				freq -= 1
				ans1 += char_var
		return ans1


class Solution:

	def Reduced_String(self, k, s):
		alpha = []
		value = []
		i = 1
		length = 1
		char = s[0]
		while i < len(s):
			if char == s[i]:
				length += 1
			else:
				alpha.append(char)
				value.append(length)
				char = s[i]
				length = 1
			i += 1
		alpha.append(char)
		value.append(length)
		i = 0
		l = 0
		while i < len(alpha):
			if value[i] >= k:
				div = value[i] % k
				if div == 0:
					value[i] = 0
					j = l
					i = i + 1
					while i < len(alpha) and j >= 0:
						if value[j] == 0:
							j -= 1
						elif alpha[i] == alpha[j]:
							value[i] = value[i] + value[j]
							value[j] = 0
							if value[i] >= k:
								if value[i] % k == 0:
									value[i] = 0
									i = i + 1
									j = j - 1
								else:
									l = i
									value[i] = value[i] % k
									i += 1
									break
							else:
								l = i
								i += 1
								break
						else:
							break
				else:
					l = i
					value[i] = div
					i += 1
			else:
				l = i
				i += 1
		res = ''
		for i in range(len(alpha)):
			res = res + alpha[i] * value[i]
		return res


class Solution:

	def Reduced_String(self, k, s):
		s = list(s)
		stack = [[s[0], 1]]
		n = len(s)
		if k == 1:
			return ''
		for i in range(1, n):
			if len(stack) == 0 or stack[-1][0] != s[i]:
				stack.append([s[i], 1])
			elif stack[-1][0] == s[i]:
				stack.append([s[i], stack[-1][1] + 1])
				if stack[-1][1] == k:
					while stack and stack[-1][0] == s[i]:
						stack.pop()
		i = len(stack) - 1
		temp = i
		while stack:
			s[i] = stack[-1][0]
			stack.pop()
			i -= 1
		return ''.join(s[:temp + 1])


class Solution:

	def Reduced_String(self, k, s):
		stk = list()
		ans = str()
		for i in range(len(s)):
			if len(stk) and stk[-1][0] == s[i]:
				(char, val) = stk.pop()
				val += 1
				stk.append([char, val])
			else:
				stk.append([s[i], 1])
			if stk[-1][1] == k:
				stk.pop()
		for i in stk:
			ans += i[0] * i[1]
		return ans


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = []
		c = 1
		for i in range(len(s)):
			if len(stack) == 0:
				stack.append([s[i], c])
			elif stack[-1][0] == s[i]:
				stack[-1][1] += 1
				if stack[-1][1] == k:
					stack.pop()
			else:
				c = 1
				stack.append([s[i], c])
		new_string = ''
		for i in stack:
			new_string += i[0] * i[1]
		return new_string


class Solution:

	def Reduced_String(self, k, s):
		stk = []
		for c in s:
			if stk and stk[-1][0] == c:
				stk[-1][1] += 1
			else:
				stk.append([c, 1])
			if stk[-1][1] >= k:
				stk.pop()
		result = ''
		for item in stk:
			result += item[0] * item[1]
		return result


class Solution:

	def Reduced_String(self, k, s):
		can = True
		while can:
			can = False
			cset = set(s)
			for ch in cset:
				if ch * k in s:
					s = s.replace(ch * k, '')
					can = True
		return s


class Solution:

	def Reduced_String(self, k, s):
		n = len(s)
		ret = ''
		i = 1
		if k == 1:
			return ''
		stack = [[s[0], 1]]
		while i < n:
			if stack:
				top = stack[-1]
				if top[0] == s[i] and top[1] == k - 1:
					stack.pop()
				elif top[0] == s[i]:
					stack[-1][1] += 1
				else:
					stack.append([s[i], 1])
			else:
				stack.append([s[i], 1])
			i += 1
		while stack:
			top = stack.pop()
			ret += top[0] * top[1]
		j = len(ret) - 1
		ret1 = ''
		while j >= 0:
			ret1 += ret[j]
			j -= 1
		return ret1


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		if k == 1:
			return ''
		for ch in s:
			if stack and stack[-1][0] == ch:
				(char, count) = stack.pop()
				stack.append((ch, count + 1))
				if stack[-1][1] == k:
					stack.pop()
			else:
				stack.append((ch, 1))
		ans = ''
		for (ch, count) in stack:
			ans += ch * count
		return ans


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		for char in s:
			if len(stack) == 0:
				stack.append([char, 1])
			elif stack[-1][0] == char:
				stack[-1][1] += 1
			else:
				stack.append([char, 1])
			if stack[-1][1] == k:
				stack.pop()
		output = ''
		for (char, freq) in stack:
			output += char * freq
		return output


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		for i in range(len(s)):
			stack.append(s[i])
			if len(stack) >= k:
				flag = True
				for j in range(k):
					if stack[-j - 1] != s[i]:
						flag = False
						break
				if flag == True:
					for l in range(k):
						stack.pop()
		return ''.join(stack)


class Solution:

	def Reduced_String(self, k, s):
		st = []
		for i in s:
			if len(st) == 0:
				st.append((i, 1))
			else:
				st_top = st[-1][0]
				if st_top == i:
					st_freq = st[-1][1]
					st.append((i, st_freq + 1))
				else:
					st.append((i, 1))
			if st[-1][1] == k:
				while len(st) > 0 and st[-1][0] == i and (st[-1][1] <= k):
					st.pop()
		return ''.join([i[0] for i in st])


class Solution:

	def Reduced_String(self, k, S):
		if k == 1:
			return ''
		stack = []
		for i in S:
			if len(stack) == 0:
				stack.append((i, 1))
			elif stack[-1][0] != i:
				stack.append((i, 1))
			else:
				frequency = stack[-1][1] + 1
				char = stack[-1][0]
				if frequency != k:
					stack.append((char, frequency))
				else:
					frequency -= 1
					while frequency > 0:
						stack.pop()
						frequency -= 1
		ans = ''
		for (i, j) in stack:
			ans += i
		return ans


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		for i in s:
			if stack == [] or stack[-1][0] != i:
				stack.append([i, 1])
			else:
				stack.append([i, stack[-1][-1] + 1])
			if stack[-1][-1] == k:
				for i in range(k):
					stack.pop()
		temp = ''
		for i in stack:
			temp += i[0]
		return temp


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		count = 0
		if k == 1:
			return ''
		for i in s:
			if not stack:
				stack.append((i, 1))
			elif stack[-1][0] != i:
				stack.append((i, 1))
			elif stack[-1][0] == i:
				count = stack[-1][1] + 1
				if k == count:
					while stack and stack[-1][0] == i:
						stack.pop()
				else:
					stack.append((i, count))
		ans = ''
		for i in stack:
			ans += i[0]
		return ans


class Solution:

	def Reduced_String(self, k, s):
		st = []
		if k == 1:
			return ''
		for i in s:
			if len(st) == 0:
				st.append([i, 1])
				continue
			if i == st[-1][0]:
				if st[-1][1] == k - 1:
					j = len(st) - 1
					c = k
					while j >= 0 and c > 1:
						st.pop()
						c -= 1
						j -= 1
				else:
					st.append([i, st[-1][1] + 1])
			else:
				st.append([i, 1])
		ans = ''
		for j in st:
			ans += j[0]
		return ans


class Solution:

	def Reduced_String(self, k, a):
		if k == 1:
			return ''
		s = []
		for i in range(len(a)):
			if s and s[-1][0] == a[i]:
				s[-1][-1] += 1
				if s[-1][-1] == k:
					s.pop()
				continue
			s.append([a[i], 1])
		res = ''
		for i in range(len(s)):
			res += s[i][0] * s[i][1]
		return res


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		n = 1
		stack.append([s[0], 1])
		if k == 1:
			return ''
		for i in range(1, len(s)):
			if len(stack) != 0:
				if stack[-1][0] == s[i]:
					n = stack[-1][1] + 1
					stack.append([s[i], n])
				else:
					n = 1
					stack.append([s[i], n])
				if stack[-1][1] == k:
					for i in range(k):
						stack.pop()
			else:
				n = 1
				stack.append([s[i], n])
		s1 = ''
		for i in range(len(stack)):
			s1 += stack[i][0]
		return s1


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = ['']
		k_a = [0]
		for i in s:
			if i == stack[-1]:
				k_a[-1] += 1
				if k_a[-1] == k:
					stack.pop()
					k_a.pop()
			else:
				stack.append(i)
				k_a.append(1)
		for i in range(len(stack)):
			stack[i] = k_a[i] * stack[i]
		return ''.join(stack)


class Pair:

	def __init__(self, char, count):
		self.char = char
		self.count = count

class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		stack = []
		for letter in s:
			if not stack:
				stack.append(Pair(letter, 1))
			elif stack[-1].char == letter:
				pair_obj = stack.pop()
				(char, count) = (pair_obj.char, pair_obj.count)
				stack.append(Pair(char, count + 1))
				if stack[-1].count == k:
					stack.pop()
			else:
				stack.append(Pair(letter, 1))
		res = ''
		for pair in stack:
			res += pair.char * pair.count
		return res


class Solution:

	def Reduced_String(self, k, s):
		if k == 1:
			return ''
		st = []
		output = []
		for ch in s:
			if st and st[-1][0] == ch:
				st[-1][1] += 1
				if st[-1][1] == k:
					st.pop()
			else:
				st.append([ch, 1])
		for list in st:
			output.append(list[0] * list[1])
		return ''.join(output)


class Solution:

	def Reduced_String(self, k, s):
		ans = []
		s1 = ''
		f = 1
		n = len(s)
		if k == 1:
			return ''
		for i in range(n):
			if len(ans) == 0:
				ans.append([s[i], 1])
			elif ans[-1][0] != s[i]:
				ans.append([s[i], 1])
			else:
				ans[-1][1] += 1
				if ans[-1][1] == k:
					ans.pop(-1)
		r = ''
		for i in ans:
			r += i[0] * i[1]
		return r


class Solution:

	def Reduced_String(self, k, s):
		if len(s) == 1:
			return s if k != 1 else ''
		if k == 1:
			return ''
		stack = [[s[0], 1]]
		pointer1 = 1
		frequency = 1
		while pointer1 < len(s):
			if len(stack) != 0:
				if s[pointer1] == stack[-1][0]:
					stack[-1][1] += 1
					if stack[-1][1] == k:
						stack.pop()
				elif s[pointer1] != stack[-1][0]:
					stack.append([s[pointer1], 1])
			else:
				stack.append([s[pointer1], 1])
			pointer1 += 1
		ans = ''
		for i in range(len(stack)):
			ans += stack[i][0] * stack[i][1]
		return ans


class Solution:

	def Reduced_String(self, k, s):
		stack = []
		for i in s:
			if stack and stack[-1][0] == i:
				(c, cnt) = stack.pop()
				stack.append((c, cnt + 1))
			else:
				stack.append((i, 1))
			if stack and stack[-1][1] == k:
				stack.pop()
		ans = ''
		for i in stack:
			ans += i[0] * i[1]
		return ans