Geek has a string Sof size Nconsisting of characters from '0'to '9'. He wants to minimise the length of the string. In each minimising operation, geek can remove any two consecutive characters if they are of the form {"12", "21", "34", "43", "56", "65", "78", "87", "09", "90"}.
Find the minimum possible length of the string after applying minimising operations. 
 
Example 1:
Input: 
N = 5 
S = "12213"
Output: 1
Explanation: Geek can get the string of 
length 1 in two minimising operation,
In 1st operation Geek will remove "12" 
from "12213" then Geek left with "213"
In 2nd operation Geek will remove "21" 
from "213" then Geek left with "3"
 
Example 2:
Input: 
N = 4
S = "1350"
Output: 4
Explanation: Can't remove any character.
 
Your Task:  
You don't need to read input or print anything. Complete the functionminLength() which takes N and S as input parameters and returns the the minimum possible length of the string.
Expected Time Complexity: O(N)
Expected Auxiliary Space:O(N)
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:
    def minLength(self, s, n): 
        #code here 

Solutions:
class Solution:

	def minLength(self, s, n):
		stack = []
		stack.append(int(s[0]))
		for ch in s[1:]:
			if stack and (int(ch) == 0 and stack[-1] == 9 or (int(ch) == 9 and stack[-1] == 0) or (int(ch) - stack[-1] == 1 and int(ch) % 2 == 0) or (stack[-1] - int(ch) == 1 and stack[-1] % 2 == 0)):
				stack.pop()
			else:
				stack.append(int(ch))
		return len(stack)


class Solution:

	def checker(self, a, b):
		if a == 1 and b == 2 or (a == 2 and b == 1):
			return True
		elif a == 3 and b == 4 or (a == 4 and b == 3):
			return True
		elif a == 5 and b == 6 or (a == 6 and b == 5):
			return True
		elif a == 7 and b == 8 or (a == 8 and b == 7):
			return True
		elif a == 0 and b == 9 or (a == 9 and b == 0):
			return True
		return False

	def minLength(self, s, n):
		stack = []
		for i in range(len(s)):
			x = int(s[i]) - 0
			if stack == []:
				stack.append(x)
			elif stack != [] and self.checker(stack[-1], x):
				stack.pop()
			elif stack != [] and (not self.checker(stack[-1], x)):
				stack.append(x)
		return len(stack)


class Solution:

	def minLength(self, s, n):
		arr = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		si = []
		si.append(s[0])
		for i in range(1, n):
			si.append(s[i])
			if len(si) > 1:
				if si[-2] + si[-1] in arr:
					si.pop()
					si.pop()
		return len(si)


class Solution:

	def minLength(self, str, n):
		l = []
		for i in str:
			l.append(i)
		s = {'12', '21', '34', '43', '56', '65', '78', '87', '09', '90'}
		i = 0
		while i < len(l) - 1:
			res = ''
			res = l[i] + l[i + 1]
			if res in s:
				l.pop(i)
				l.pop(i)
				if i != 0:
					i -= 1
				else:
					i = 0
			else:
				i += 1
		return len(l)


class Solution:

	def minLength(self, s, n):
		s1 = ('12', '21', '34', '43', '56', '65', '78', '87', '09', '90')
		s1 = set(s1)
		j = 0
		stack = []
		stack.append(s[0])
		i = 1
		while i < n:
			if len(stack) > 0 and stack[-1] + s[i] in s1:
				stack.pop()
			else:
				stack.append(s[i])
			i += 1
		return len(stack)


class Solution:

	def minLength(self, s, n):
		stack = []
		for c in s:
			if len(stack) == 0:
				stack.append(c)
			elif c == '1' and stack[-1] == '2':
				stack.pop()
			elif c == '2' and stack[-1] == '1':
				stack.pop()
			elif c == '3' and stack[-1] == '4':
				stack.pop()
			elif c == '4' and stack[-1] == '3':
				stack.pop()
			elif c == '5' and stack[-1] == '6':
				stack.pop()
			elif c == '6' and stack[-1] == '5':
				stack.pop()
			elif c == '7' and stack[-1] == '8':
				stack.pop()
			elif c == '8' and stack[-1] == '7':
				stack.pop()
			elif c == '9' and stack[-1] == '0':
				stack.pop()
			elif c == '0' and stack[-1] == '9':
				stack.pop()
			else:
				stack.append(c)
		return len(stack)


class Solution:

	def minLength(self, s, n):
		tc = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		stack = []
		for i in s:
			if stack and stack[-1] + i in tc:
				stack.pop()
			else:
				stack.append(i)
		c = 0
		while stack:
			c += 1
			stack.pop()
		return c


class Solution:

	def minLength(self, s, n):
		map1 = {'12': 1, '21': 1, '34': 1, '43': 1, '56': 1, '65': 1, '78': 1, '87': 1, '09': 1, '90': 1}
		stack = [s[0]]
		for i in range(1, n):
			if stack:
				if str(stack[-1] + s[i]) in map1:
					stack.pop()
				else:
					stack.append(s[i])
			else:
				stack.append(s[i])
		return len(stack)


class Solution:

	def minLength(self, s, n):
		setti = set(['12', '21', '34', '43', '56', '65', '78', '87', '90', '09'])
		stack = []
		for item in s:
			if stack and stack[-1] + item in setti:
				stack.pop()
			else:
				stack.append(item)
		return len(stack)


class Solution:

	def minLength(self, s, n):
		l = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		y = 0
		stack = []
		for i in s:
			y += 1
			if stack:
				if stack[-1] + i in l:
					stack.pop()
					y -= 2
				else:
					stack.append(i)
			else:
				stack.append(i)
		return y


class Solution:

	def minLength(self, s, n):
		l = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		i = 0
		while i < len(l):
			if l[i] in s:
				s = s.replace(l[i], '')
				i = 0
			else:
				i += 1
		return len(s)


class Solution:

	def minLength(self, s, n):
		x = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		ans = []
		for i in s:
			if not ans:
				ans.append(i)
			elif ans[-1] + i in x:
				ans.pop()
			else:
				ans.append(i)
		return len(ans)


class Solution:

	def minLength(self, s, n):

		def expected(num):
			if num == '0':
				return '9'
			if num == '9':
				return '0'
			if int(num) % 2 == 0:
				return str(int(num) - 1)
			return str(int(num) + 1)
		stack = []
		for i in range(n):
			if len(stack) == 0:
				stack.append(s[i])
			elif stack[-1] == expected(s[i]):
				stack.pop()
			else:
				stack.append(s[i])
		return len(stack)


class Solution:

	def minLength(self, s, n):
		set1 = set('12')
		set2 = set('34')
		set3 = set('56')
		set4 = set('78')
		set5 = set('90')
		stack = []
		arr = [*s]
		while arr:
			if not stack:
				stack.append(arr.pop())
			elif set([stack[-1], arr[-1]]) == set1:
				stack.pop()
				arr.pop()
			elif set([stack[-1], arr[-1]]) == set2:
				stack.pop()
				arr.pop()
			elif set([stack[-1], arr[-1]]) == set3:
				stack.pop()
				arr.pop()
			elif set([stack[-1], arr[-1]]) == set4:
				stack.pop()
				arr.pop()
			elif set([stack[-1], arr[-1]]) == set5:
				stack.pop()
				arr.pop()
			else:
				stack.append(arr.pop())
		return len(stack)


class Solution:

	def minLength(self, s, n):
		lisof = ['21', '12', '34', '43', '56', '65', '78', '87', '09', '90']
		st = []
		for i in s:
			if st and i + st[-1] in lisof:
				st.pop()
			else:
				st.append(i)
		return len(st)


class Solution:

	def minLength(self, s, n):
		res = []
		temp = {'12', '21', '34', '43', '56', '65', '78', '87', '09', '90'}
		for i in s:
			if res == []:
				res.append(i)
			elif res[-1] + i in temp:
				res.pop()
			else:
				res.append(i)
		return len(res)


class Solution:

	def minLength(self, s, n):
		forms = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		stack = []
		for i in range(n - 1, -1, -1):
			stack.append(s[i])
			if len(stack) >= 2 and stack[-1] + stack[-2] in forms:
				stack.pop()
				stack.pop()
		return len(stack)


class Solution:

	def minLength(self, s, n):
		stack = []
		ind = 0
		ref = {1: 2, 2: 1, 3: 4, 4: 3, 5: 6, 6: 5, 7: 8, 8: 7, 0: 9, 9: 0}
		while ind < n:
			if stack and stack[-1] == ref[int(s[ind])]:
				stack.pop()
			else:
				stack.append(int(s[ind]))
			ind += 1
		return len(stack)


class Solution:

	def minLength(self, S, n):
		s = {'12', '21', '34', '43', '56', '65', '78', '87', '09', '90'}
		st = []
		for i in range(len(S)):
			if len(st) < 2:
				st.append(S[i])
			else:
				if ''.join(st[-1:-3:-1]) in s:
					st.pop()
					st.pop()
				st.append(S[i])
		if ''.join(st[-1:-3:-1]) in s:
			st.pop()
			st.pop()
		return len(st)


class Solution:

	def minLength(self, s, n):
		lst = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		stack = []
		count1 = n
		i = 0
		while i < n:
			if len(stack) == 0:
				stack.append(s[i])
			else:
				x = stack.pop(-1)
				if str(x) + str(s[i]) in lst:
					count1 -= 2
				else:
					stack.append(x)
					stack.append(s[i])
			i += 1
		return count1


class Solution:

	def minLength(self, s, n):
		a = []
		for i in s:
			if a == []:
				x = int(i)
				a.append(x)
			else:
				x = int(i)
				if a[len(a) - 1] == 9 and x == 0:
					a.pop()
				elif a[len(a) - 1] == 0 and x == 9:
					a.pop()
				elif a[len(a) - 1] == 1 and x == 2:
					a.pop()
				elif a[len(a) - 1] == 2 and x == 1:
					a.pop()
				elif a[len(a) - 1] == 3 and x == 4:
					a.pop()
				elif a[len(a) - 1] == 4 and x == 3:
					a.pop()
				elif a[len(a) - 1] == 5 and x == 6:
					a.pop()
				elif a[len(a) - 1] == 6 and x == 5:
					a.pop()
				elif a[len(a) - 1] == 7 and x == 8:
					a.pop()
				elif a[len(a) - 1] == 8 and x == 7:
					a.pop()
				else:
					a.append(int(x))
		return len(a)


class Solution:

	def minLength(self, s, n):
		a = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		st = []
		for i in range(n):
			if len(st) == 0:
				st.append(s[i])
			else:
				temp = ''
				temp += st[-1]
				temp += s[i]
				if temp in a:
					st.pop()
				else:
					st.append(s[i])
		return len(st)


class Solution:

	def minLength(self, s, n):
		sta = []
		for i in range(n):
			sta.append(s[i])
			d = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
			while len(sta) >= 2 and ''.join(sta[-1:-3:-1]) in d:
				sta.pop()
				sta.pop()
		return len(sta)


class Solution:

	def minLength(self, s, n):
		s1 = {'12', '21', '34', '43', '56', '65', '78', '87', '09', '90'}
		p1 = 0
		p2 = 1
		while len(s) >= 2 and p2 < len(s):
			if s[p1:p2 + 1] in s1:
				s = s.replace(s[p1:p2 + 1], '')
				p1 = 0
				p2 = 1
			else:
				p1 += 1
				p2 += 1
		return len(s)


class Solution:

	def minLength(self, s, n):
		stack = ''
		st = {'12', '21', '34', '43', '56', '65', '78', '87', '09', '90'}
		for c in s:
			stack += c
			if len(stack) >= 2:
				if stack[-1] + stack[-2] in st:
					stack = stack[:-2]
		return len(stack)


class Solution:

	class Stack:

		class Node:

			def __init__(self, value):
				self.val = value
				self.prev = None

			def __repr__(self):
				return str(self.val)

		def __init__(self, value=None):
			if value:
				self.head = self.Node(value)
			else:
				self.head = None

		def __repr__(self):
			if self.head == None:
				return ''
			trans = self.head
			repr_str = str(self.head.val)
			while trans.prev:
				repr_str += ' -> ' + str(trans.prev.val)
				trans = trans.prev
			return repr_str

		def push(self, value):
			if self.head:
				new_node = self.Node(value)
				new_node.prev = self.head
				self.head = new_node
			else:
				self.head = self.Node(value)
			return None

		def pop(self):
			if self.head:
				val = self.head.val
				self.head = self.head.prev
				return val
			else:
				return None

		def glance(self):
			if self.head:
				return self.head.val
			else:
				return None

	def minLength(self, s, n):
		pairs = {'1': '2', '2': '1', '3': '4', '4': '3', '5': '6', '6': '5', '7': '8', '8': '7', '9': '0', '0': '9'}
		stack = self.Stack()
		count = 0
		for element in s:
			if pairs.get(element) == stack.glance():
				stack.pop()
				count -= 1
			else:
				stack.push(element)
				count += 1
		return count


class Solution:

	def minLength(self, s, n):
		check_list = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		str = ''
		i = 0
		if n == 1:
			return n
		while i < n - 1:
			if s[i:i + 2] not in check_list:
				str = str + s[i]
				i = i + 1
			else:
				i = i + 2
		if i == n - 1:
			str = str + s[i]
		if len(str) == n:
			return n
		else:
			return self.minLength(str, len(str))


class Solution:
	table = {'1': '2', '2': '1', '3': '4', '4': '3', '5': '6', '6': '5', '7': '8', '8': '7', '9': '0', '0': '9'}

	def peek(self, stack):
		if stack == []:
			return None
		return stack[-1]

	def minLength(self, s, n):
		stack = []
		for c in s:
			if self.peek(stack) == self.table[c]:
				stack.pop()
			else:
				stack.append(c)
		return len(stack)


class Solution:

	def minLength(self, s, n):
		temp_str = ''
		stack = []
		pattern = {'12', '21', '34', '43', '56', '65', '78', '87', '09', '90'}
		for idx in range(n):
			temp_str += s[idx]
			if len(temp_str) == 2:
				if temp_str in pattern:
					stack.pop()
					temp_str = stack[-1] if len(stack) > 0 else ''
				else:
					stack.append(s[idx])
					temp_str = temp_str.replace(temp_str[0], '', 1)
			else:
				stack.append(s[idx])
		return len(stack)


class Solution:

	def minLength(self, s, n):
		t = [(int(e), (int(e) + int(e) % 2) % 10) for e in s]
		while True:
			s = []
			i = 0
			while i < len(t):
				if i < len(t) - 1 and t[i][0] != t[i + 1][0] and (t[i][1] == t[i + 1][1]):
					i += 2
				else:
					s.append(t[i])
					i += 1
			if s == t:
				break
			t = s
		return len(t)


class Solution:

	def minLength(self, s, n):
		s = list(s)
		l2 = []
		arr = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		for i in range(n):
			if len(s) == 0:
				break
			popped = s.pop(0)
			if len(l2) != 0:
				if l2[-1] + popped in arr:
					l2.pop(-1)
					continue
			if len(s) != 0:
				top = s[0]
			else:
				top = ''
			ss = popped + top
			if ss in arr:
				s.pop(0)
			else:
				l2.append(popped)
		return len(l2)


class Solution:

	def minLength(self, s, n):
		i = 0
		set1 = {'12', '21', '34', '43', '56', '65', '78', '87', '09', '90'}
		while i < len(s) - 1:
			s1 = s[i] + s[i + 1]
			if s1 in set1:
				if i > 0:
					s = s[:i] + s[i + 2:]
					i = max(0, i - 1)
				else:
					s = s[i + 2:]
			else:
				i += 1
		return len(s)


class Solution:

	def minLength(self, s, n):
		l = ['12', '21', '34', '43', '56', '65', '78', '87', '90', '09']
		ln = len(s)
		while True:
			c = 0
			for i in l:
				if i in s:
					c = 1
					e = i
			if c == 1:
				s = s.replace(e, '')
			else:
				break
		return len(s)


class Solution:

	def minLength(self, s, n):
		chars = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		dic = dict.fromkeys(chars)
		stack = []
		for i in s:
			stack.append(i)
			if len(stack) > 1:
				char = stack[-2] + stack[-1]
				if char in dic:
					stack.pop()
					stack.pop()
		return len(stack)


class Solution:

	def minLength(self, s, n):
		stg = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		while True:
			stlen = len(s)
			for i in stg:
				s = s.replace(i, '')
			if stlen == len(s):
				break
		return len(s)


class Solution:

	def minLength(self, s, n):
		b = len(s)
		a = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		d = 0
		c = 1
		while len(s) >= 2 and c < len(s):
			if s[d:c + 1] in a:
				s = s.replace(s[d:c + 1], '')
				d = 0
				c = 1
			else:
				d += 1
				c += 1
		return len(s)


class Solution:

	def minLength(self, s, n):
		subs = [9, 2, 1, 4, 3, 6, 5, 8, 7, 0]
		stack = []
		for i in range(n):
			key = int(s[i])
			if not stack:
				stack.append(key)
			elif stack[-1] == subs[key]:
				stack.pop()
			else:
				stack.append(key)
		return len(stack)


class Solution:

	def minLength(self, s, n):
		l = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		stack = []
		top = -1
		for i in range(n):
			if top == -1:
				top = 0
				stack.append(s[i])
				continue
			c = ''
			c += stack[top]
			c += s[i]
			if c in l:
				stack.pop(top)
				top -= 1
			else:
				stack.append(s[i])
				top += 1
		return len(stack)


class Solution:

	def minLength(self, s, n):

		def compliment(c):
			if c == '9':
				return '0'
			if c == '0':
				return '9'
			if int(c) % 2 == 0:
				return str(int(c) - 1)
			else:
				return str(int(c) + 1)
		stack = []
		counter = 0
		while counter < n:
			if len(stack) == 0:
				stack.append(s[counter])
			elif stack[-1] == compliment(s[counter]):
				stack.pop()
			else:
				stack.append(s[counter])
			counter += 1
		return len(stack)


class Solution:

	def minLength(self, s, n):
		s = [int(i) for i in s]
		pairs = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		for j in range(10):
			i = len(s) - 1
			while i > 0:
				if str(s[i]) + str(s[i - 1]) in pairs:
					s.pop(i)
					s.pop(i - 1)
					i -= 2
					continue
				i -= 1
		return len(s)


class Solution:

	def minLength(self, s, n):
		lis = ['12', '21', '34', '43', '56', '65', '78', '87', '09', '90']
		cnt = 0
		ind = 0
		stk = list()
		while ind < n:
			if stk and stk[-1] + s[ind] in lis:
				stk.pop()
			else:
				stk.append(s[ind])
			ind += 1
		return len(stk)