Rohan is downloading the movie Tiger Zinda Hai using a torrent website, but he is new to torrent, so he doesn't know the difference between a fake download button and a real download button; therefore, he keeps pressing every button in excitement.
Now he has clicked N  buttons, and many tabs are opened, if an opened tab is clicked again then it closes it. 
Your task is to tell how many tabs are open at the end.
Example 1:
Input : Arr[] = {"1", "2", "1", "END", "2"}
Output : 1
Explanation:
In the above test case, firstly tab 
1st is opened then 2nd is opened then 
1st is closed then all are closed
then again 2nd is opened.
Example 2:
Input : Arr[] = {"1", "2", "END"}
Output : 0
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function count_tabs() that takes an array of String (arr), sizeOfArray (n), and return how many tabs are open at the end. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def areElementsContiguous (self,arr, n) : 
        #Complete the function




Solutions:
class Solution:

	def areElementsContiguous(self, arr, n):
		arr = arr[::-1]
		d = {}
		c = 0
		for i in arr:
			if i == 'END':
				break
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in d:
			if d[i] % 2 != 0:
				c += 1
		return c


class Solution:

	def areElementsContiguous(self, arr, n):
		dist = []
		for x in range(len(arr)):
			if arr[x] not in dist and arr[x] != 'END':
				dist.append(arr[x])
			elif arr[x] in dist and arr[x] != 'END':
				dist.remove(arr[x])
			elif arr[x] == 'END':
				dist = []
		return len(dist)


class Solution:

	def areElementsContiguous(self, arr, n):
		count = set()
		for i in arr[::-1]:
			if i == 'END':
				break
			elif i in count:
				count.remove(i)
			else:
				count.add(i)
		return len(count)


class Solution:

	def areElementsContiguous(self, arr, n):
		result = set()
		for item in arr[::-1]:
			if item == 'END':
				break
			elif item in result:
				result.remove(item)
			else:
				result.add(item)
		return len(result)


class Solution:

	def areElementsContiguous(self, arr, n):
		c = 1000000000000000
		for i in range(n):
			if arr[i] == 'END':
				c = i
		if c == n - 1:
			return 0
		elif 'END' not in arr:
			k = 0
			j = list(set(arr))
			for i in range(len(j)):
				if arr.count(j[i]) % 2 == 1:
					k = k + 1
			return k
		elif c < n - 1:
			k = 0
			p = []
			p[:] = arr[c + 1:n]
			j = list(set(arr[c + 1:n]))
			for i in range(len(j)):
				if p.count(j[i]) % 2 == 1:
					k = k + 1
			return k


class Solution:

	def areElementsContiguous(self, arr, n):
		dic = {}
		count = 0
		for i in arr[::-1]:
			if i == 'END':
				break
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
		for i in dic:
			if dic[i] % 2 != 0:
				count += 1
		return count


class Solution:

	def areElementsContiguous(self, arr, n):
		if n > 1:
			index = n - 1
			for i in range(n - 1, -2, -1):
				index = i
				if arr[i] == 'END':
					break
			s = {}
			for i in range(index + 1, n, 1):
				if arr[i] in s:
					s[arr[i]] += 1
				else:
					s[arr[i]] = 1
			count = 0
			for i in s:
				if s[i] % 2 != 0:
					count += 1
			return count
		return 1


class Solution:

	def areElementsContiguous(self, arr, n):
		freq = set()
		for i in arr:
			if i == 'END':
				freq.clear()
			elif i not in freq:
				freq.add(i)
			elif i in freq:
				freq.remove(i)
		return len(freq)


class Solution:

	def areElementsContiguous(self, arr, n):
		res = set()
		for i in arr:
			if i in res:
				res.remove(i)
			elif i == 'END':
				res.clear()
				continue
			else:
				res.add(i)
		return len(res)


class Solution:

	def areElementsContiguous(self, arr, n):
		dict_ = {}
		opened = 0
		for elem in arr:
			if elem == 'END':
				opened = 0
				dict_ = {}
			elif elem not in dict_:
				dict_[elem] = 1
				opened += 1
			elif elem in dict_:
				del dict_[elem]
				opened -= 1
		return opened


class Solution:

	def areElementsContiguous(self, arr, n):
		a = []
		for i in arr[::-1]:
			if i == 'END':
				break
			elif i in a:
				a.remove(i)
			else:
				a.append(i)
		return len(a)


class Solution:

	def areElementsContiguous(self, arr, n):
		counter = []
		for item in arr:
			if item == 'END':
				counter = []
			elif item not in counter:
				counter.append(item)
			else:
				counter.remove(item)
		return len(counter)


class Solution:

	def areElementsContiguous(self, arr, n):
		count = 0
		arr = arr[::-1]
		if 'END' not in arr:
			x = arr[:]
		else:
			x = arr[:arr.index('END')]
		for i in set(x):
			count = count + x.count(i) % 2
		return count


class Solution:

	def areElementsContiguous(self, arr, n):
		b = []
		for i in arr:
			if i != 'END':
				if i in b:
					b.remove(i)
				else:
					b.append(i)
			else:
				b = []
		return len(b)


class Solution:

	def areElementsContiguous(self, arr, n):
		lst = [0] * 1000
		for i in arr:
			if i == 'END':
				lst = [0] * 1000
			elif lst[int(i)] == 1:
				lst[int(i)] -= 1
			else:
				lst[int(i)] += 1
		cnt = 0
		for i in lst:
			if i == 1:
				cnt += 1
		return cnt


class Solution:

	def areElementsContiguous(self, arr, n):
		di = {}
		count = 0
		for i in arr:
			if i == 'END':
				di.clear()
				continue
			if i not in di:
				di[i] = 1
			else:
				di[i] += 1
		for i in di:
			if di[i] % 2 != 0:
				count += 1
		return count


class Solution:

	def areElementsContiguous(self, arr, n):
		h = {}
		for i in range(n):
			if arr[i] == 'END':
				while len(h):
					del h
					h = {}
			elif arr[i] in h:
				if h[arr[i]] - 1 == 0:
					del h[arr[i]]
				else:
					h[arr[i]] -= 1
			else:
				h[arr[i]] = 1
		return len(h)


class Solution:

	def areElementsContiguous(self, arr, n):
		result = {}
		for item in arr:
			if item in result:
				del result[item]
			else:
				result[item] = 1
			if item == 'END':
				result = {}
		return len(result)


class Solution:

	def areElementsContiguous(self, arr, n):
		st = []
		for i in range(n):
			if arr[i] == 'END':
				st.clear()
			elif arr[i] in st:
				st.remove(arr[i])
			else:
				st.append(arr[i])
		return len(st)


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		for i in arr:
			if i not in d and i != 'END':
				d[i] = 1
			elif i == 'END':
				d.clear()
			else:
				d.pop(i)
		return len(d)


class Solution:

	def areElementsContiguous(self, arr, n):
		l = []
		l1 = []
		for i in range(n):
			if arr[i] == 'END':
				l.append(i)
		if len(l) != 0:
			del arr[:l[-1] + 1]
		for j in arr:
			if j not in l1:
				l1.append(j)
			else:
				l1.remove(j)
		return len(l1)


class Solution:

	def areElementsContiguous(self, arr, n):
		dict1 = {}
		for key in arr:
			if key == 'END':
				dict1.clear()
				continue
			dict1[key] = dict1.get(key, 0) + 1
			if dict1[key] == 2:
				dict1[key] = 0
		count = 0
		for key in dict1:
			if dict1[key] == 1:
				count = count + 1
		return count


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		for i in arr:
			if i != 'END':
				if i in d.keys():
					d[i] = (d[i] + 1) % 2
				else:
					d[i] = 1
			else:
				d.clear()
		s = 0
		for i in d.values():
			s = s + i
		return s


class Solution:

	def areElementsContiguous(self, arr, n):
		ans = 0
		mp = {}
		for i in arr:
			if i == 'END':
				ans = 0
				mp.clear()
				continue
			mp[i] = mp.get(i, 0) + 1
			if mp[i] == 2:
				mp[i] = 0
				ans -= 1
			else:
				ans += 1
		return ans


class Solution:

	def areElementsContiguous(self, arr, n):
		hm = {}
		for i in range(n - 1, -1, -1):
			if arr[i] == 'END':
				break
			if arr[i] not in hm:
				hm[arr[i]] = 1
			else:
				del hm[arr[i]]
		return len(hm)


class Solution:

	def areElementsContiguous(self, arr, n):
		res = []
		for i in range(n - 1, -1, -1):
			if arr[i] == 'END':
				break
			if arr[i] not in res:
				res.append(arr[i])
			else:
				res.remove(arr[i])
		return len(res)


class Solution:

	def areElementsContiguous(self, arr, n):
		dict = {}
		for i in arr:
			if i == 'END':
				dict = {}
			elif i in dict:
				dict[i] -= 1
				if dict[i] == 0:
					del dict[i]
			else:
				dict[i] = 1
		return len(dict.keys())


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		for i in arr:
			if i == 'END':
				d.clear()
			elif i in d:
				d.pop(i)
			else:
				d[i] = 1
		x = list(d.values())
		return x.count(1)


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		for i in range(n - 1, -1, -1):
			if arr[i] == 'END':
				break
			if arr[i] not in d:
				d[arr[i]] = 1
			elif d[arr[i]] > 0:
				del d[arr[i]]
			else:
				d[arr[i]] += 1
		return len(d)


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		c = 0
		for i in range(n - 1, -1, -1):
			if arr[i] == 'END':
				break
			elif arr[i] in d:
				d[arr[i]] += 1
			else:
				d[arr[i]] = 1
		if arr[n - 1] == 'END':
			return 0
		for (key, value) in d.items():
			if d[key] % 2 != 0:
				c += 1
		return c


class Solution:

	def areElementsContiguous(self, arr, n):
		ans = 0
		if 'END' not in arr:
			dis = {}
			for x in arr:
				if x in dis:
					dis[x] += 1
				else:
					dis[x] = 1
			for x in set(arr):
				ans += dis[x] % 2
			return ans
		else:
			arr = arr[::-1]
			end = arr.index('END')
			newArr = arr[:end]
			dis = {}
			for x in newArr:
				if x in dis:
					dis[x] += 1
				else:
					dis[x] = 1
			for x in set(newArr):
				ans += dis[x] % 2
			return ans


class Solution:

	def areElementsContiguous(self, arr, n):
		count = []
		temp = []
		for i in range(n):
			if arr[i] == 'END':
				count = []
				temp = []
			elif arr[i] not in temp:
				temp.append(arr[i])
				count.append(1)
			else:
				pos = temp.index(arr[i])
				count[pos] += 1
		sum = 0
		for ele in count:
			sum += ele % 2
		return sum


class Solution:

	def areElementsContiguous(self, arr, n):
		p = []
		for i in range(n):
			if arr[i] == 'END':
				p.clear()
			elif arr[i] in p:
				p.remove(arr[i])
			else:
				p.append(arr[i])
		return len(p)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(str, input().strip().split()))
	ob = Solution()
	res = ob.areElementsContiguous(arr, n)
	print(res)


class Solution:

	def areElementsContiguous(self, arr, n):
		kt = {}
		for x in arr:
			if x == 'END':
				kt = {}
			elif x in kt.keys():
				kt[x] += 1
			else:
				kt[x] = 1
		ct = 0
		for x in kt.keys():
			if kt[x] % 2 != 0:
				ct += 1
		return ct
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(str, input().strip().split()))
	ob = Solution()
	res = ob.areElementsContiguous(arr, n)
	print(res)


class Solution:

	def areElementsContiguous(self, arr, n):
		s = {}
		for i in arr:
			if i == 'END':
				for i in s:
					s[i] = 0
			elif i in s:
				s[i] = s[i] ^ 1
			else:
				s[i] = 1
		c = 0
		for i in s:
			if s[i] == 1:
				c += 1
		return c
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(str, input().strip().split()))
	ob = Solution()
	res = ob.areElementsContiguous(arr, n)
	print(res)


class Solution:

	def areElementsContiguous(self, arr, n):
		if 'END' in arr:
			arr.reverse()
			indx = arr.index('END')
			arr.reverse()
		else:
			indx = n
		lst = []
		for itr in range(n - indx, n):
			if arr[itr] not in lst:
				lst.append(arr[itr])
			else:
				lst.remove(arr[itr])
		return len(lst)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(str, input().strip().split()))
	ob = Solution()
	res = ob.areElementsContiguous(arr, n)
	print(res)


class Solution:

	def areElementsContiguous(self, arr, n):
		if arr[-1] == 'END':
			return 0
		dic = {}
		for i in arr:
			if i not in dic:
				dic[i] = 1
			else:
				dic[i] += 1
			if i == 'END':
				dic.clear()
		count = 0
		for (k, v) in dic.items():
			if v % 2 != 0:
				count += 1
		return count
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(str, input().strip().split()))
	ob = Solution()
	res = ob.areElementsContiguous(arr, n)
	print(res)


from collections import Counter as C

class Solution:

	def areElementsContiguous(self, a, n):
		if a[-1] == 'END':
			return 0
		if n == 1:
			return 1
		t = 0
		for i in range(n - 1, -1, -1):
			if a[i] == 'END':
				t = i
				break
		if t:
			a = a[t + 1:]
		z = 0
		for (i, j) in C(a).items():
			z += j & 1
		return z


class Solution:

	def areElementsContiguous(self, arr, n):
		d = dict()
		for i in arr:
			if i != 'END':
				if i in d.keys():
					d[i] = (d[i] + 1) % 2
				else:
					d[i] = 1
			else:
				d.clear()
		s = 0
		for i in d.values():
			s = s + int(i)
		return s
		hash = {}
		res = 0
		for i in arr:
			if i == 'END':
				hash = {}
				continue
			if i in hash:
				temp = hash[i]
				del hash[temp]
			else:
				hash[i] = 1
		for (key, value) in hash.items():
			print(key, value)
			if value == 1:
				res += 1
		return res


class Solution:

	def areElementsContiguous(self, arr, n):
		unique = []
		for i in range(n):
			if arr[i] == 'END':
				unique.clear()
			elif arr[i] in unique:
				unique.remove(str(arr[i]))
			elif arr[i] not in unique:
				unique.append(str(arr[i]))
		return len(unique)


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		for i in arr:
			if i in d and d[i] > 0:
				d[i] -= 1
			else:
				d[i] = 1
			if i == 'END':
				d = {}
		return sum(d.values())


class Solution:

	def areElementsContiguous(self, arr, n):
		hm = {}
		for i in arr:
			if i in hm:
				del hm[i]
			elif i == 'END':
				hm.clear()
			else:
				hm[i] = 1
		return len(hm)


class Solution:

	def areElementsContiguous(self, arr, n):
		opened = []
		for x in arr:
			if x == 'END':
				opened.clear()
			elif x not in opened:
				opened.append(x)
			else:
				opened.remove(x)
		return len(opened)


class Solution:

	def areElementsContiguous(self, arr, n):
		count = 0
		d = {}
		for ele in arr[::-1]:
			if ele == 'END':
				break
			else:
				d[ele] = d.get(ele, 0) + 1
		for (key, value) in d.items():
			if value % 2 != 0:
				count = count + 1
		return count


class Solution:

	def areElementsContiguous(self, arr, n):
		dict = {}
		for i in arr:
			if i == 'END':
				dict = {}
			elif i in dict:
				dict.pop(i)
			else:
				dict[i] = 1
		return len(dict)


class Solution:

	def areElementsContiguous(self, arr, n):
		stts = {}
		for i in range(0, n):
			if arr[i] == 'END':
				stts = {}
				continue
			try:
				if stts[arr[i]] == 0:
					stts[arr[i]] += 1
				else:
					stts[arr[i]] -= 1
			except:
				stts[arr[i]] = 1
		c = 0
		for i in stts:
			c += stts[i]
		return c


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		ans = 0
		for i in range(n - 1, -1, -1):
			if arr[i] == 'END':
				return ans
			if arr[i] in d.keys():
				if d[arr[i]] == 1:
					ans -= 1
					d[arr[i]] = 0
				else:
					ans += 1
					d[arr[i]] = 1
			else:
				d[arr[i]] = 1
				ans += 1
		return ans


class Solution:

	def areElementsContiguous(self, arr, n):
		dic = {}
		for i in arr:
			if i == 'END':
				dic.clear()
			elif i not in dic.keys():
				dic[i] = 'open'
			else:
				dic.pop(i)
		return len(dic)


class Solution:

	def areElementsContiguous(self, arr, n):
		l = []
		l1 = []
		if 'END' in arr:
			for i in range(len(arr)):
				if arr[i] == 'END':
					l.append(i)
			k = l[-1]
			a = arr[k + 1:]
			for i in a:
				k = a.count(i)
				if k % 2 == 1:
					l1.append(i)
			o = list(set(l1))
			return len(o)
		else:
			for i in arr:
				k = arr.count(i)
				if k % 2 == 1:
					l1.append(i)
			o = list(set(l1))
			return len(o)


class Solution:

	def areElementsContiguous(self, arr, n):
		dic = {}
		for i in arr:
			if i == 'END':
				dic = {}
			else:
				dic[i] = dic.get(i, 0) + 1
				if dic[i] % 2 == 0:
					dic.pop(i)
		return len(dic.keys())


class Solution:

	def areElementsContiguous(self, arr, n):
		freq = dict()
		for i in range(len(arr)):
			el = arr[i]
			if el == 'END':
				freq.clear()
			elif el not in freq.keys():
				freq[el] = 1
			elif freq[el] == 0:
				freq[el] = 1
			elif freq[el] == 1:
				freq[el] = 0
		c = 0
		for (key, value) in freq.items():
			if value == 1:
				c += 1
		return c


class Solution:

	def areElementsContiguous(self, arr, n):
		d = {}
		c = 0
		for i in arr:
			if i in d:
				del d[i]
			elif i == 'END':
				d = {}
			else:
				d[i] = True
		return len(d)