Given an input stream A of n characters consisting only of lower case alphabets. While reading characters from the stream, you have to tell which character has appeared only once in the stream upto that point. If there are many characters that have appeared only once, you have to tell which one of them was the first one to appear. If there is no such character then append '#' to the answer.
 
Example 1:
Input: A = "aabc"
Output: "a#bb"
Explanation: For every character first non
repeating character is as follow-
"a" - first non-repeating character is 'a'
"aa" - no non-repeating character so '#'
"aab" - first non-repeating character is 'b'
"aabc" - first non-repeating character is 'b'
Example 2:
Input: A = "zz"
Output: "z#"
Explanation: For every character first non
repeating character is as follow-
"z" - first non-repeating character is 'z'
"zz" - no non-repeating character so '#'
 
Your Task:
You don't need to read or print anything. Your task is to complete the function FirstNonRepeating() which takes A as input parameter and returns a string after processing the input stream.
 
Expected Time Complexity: O(26 * n)
Expected Space Complexity: O(26)
 
Constraints:
1 <= n <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

	def FirstNonRepeating(self, A):

		# Code here

Solutions:
from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		count = {}
		queue = deque()
		result = ''
		for char in A:
			count[char] = count.get(char, 0) + 1
			if count[char] == 1:
				queue.append(char)
			while queue and count[queue[0]] > 1:
				queue.popleft()
			if queue:
				result += queue[0]
			else:
				result += '#'
		return result


class Solution:

	def FirstNonRepeating(self, A):
		q = []
		dic = {}
		ans = []
		for i in A:
			q.append(i)
			dic[i] = 1 + dic.get(i, 0)
			while q:
				if dic[q[0]] > 1:
					q.pop(0)
				else:
					ans.append(q[0])
					break
			if len(q) == 0:
				ans.append('#')
		return ''.join(ans)


class Solution:

	def FirstNonRepeating(self, arr):
		count = [0] * 26
		ans = ''
		q = []
		for i in range(len(arr)):
			count[ord(arr[i]) - ord('a')] += 1
			q.append(arr[i])
			while len(q) != 0:
				if count[ord(q[0]) - ord('a')] > 1:
					q.pop(0)
				else:
					ans += q[0]
					break
			if len(q) == 0:
				ans += '#'
		return ans


from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		q = deque()
		visit = [0] * 26
		visit1 = [0] * 26
		ans = []
		for i in range(len(A)):
			t = A[i]
			x = ord(t) - 97
			if visit[x] == 0:
				q.append(t)
				visit[x] = 1
			elif visit1[x] == 0:
				q.remove(t)
				visit1[x] = 1
			if len(q) == 0:
				ans.append('#')
			else:
				ans.append(q[0])
		return ''.join(ans)


class Solution:

	def FirstNonRepeating(self, A):
		from collections import defaultdict, deque
		freq = defaultdict(int)
		queue = deque()
		result = ''
		for i in A:
			freq[i] += 1
			queue.append(i)
			while queue and freq[queue[0]] > 1:
				queue.popleft()
			if not queue:
				result += '#'
			else:
				result += queue[0]
		return result


class Solution:

	def FirstNonRepeating(self, stream):
		hm = {}
		queue = []
		ans = ''
		for i in stream:
			if i in hm:
				hm[i] += 1
			else:
				hm[i] = 1
			queue.append(i)
			while queue:
				if hm[queue[0]] > 1:
					queue.pop(0)
				else:
					ans += queue[0]
					break
			if not queue:
				ans += '#'
		return ans


from collections import defaultdict, deque

class Solution:

	def FirstNonRepeating(self, A):
		freq = defaultdict(int)
		q = deque()
		ans = []
		for c in A:
			freq[c] += 1
			q.append(c)
			while q and freq[q[0]] > 1:
				q.popleft()
			if q:
				ans.append(q[0])
			else:
				ans.append('#')
		return ''.join(ans)


from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		q = [A[0]]
		d = {}
		d[A[0]] = 1
		res = [A[0]]
		for i in range(1, len(A)):
			if A[i] not in d:
				d[A[i]] = d.get(A[i], 0) + 1
				q.append(A[i])
			elif A[i] in q:
				q.remove(A[i])
			if q == []:
				res.append('#')
			else:
				res.append(q[0])
		return ''.join(res)


from collections import defaultdict

class Solution:

	def FirstNonRepeating(self, A):
		count = defaultdict(int)
		q = []
		ans = ''
		for char in A:
			count[char] += 1
			q.append(char)
			while q:
				if count[q[0]] > 1:
					q.pop(0)
				else:
					ans += q[0]
					break
			if len(q) == 0:
				ans += '#'
		return ans


from collections import defaultdict

class Solution:

	def FirstNonRepeating(self, A):
		d = defaultdict(int)
		l = []
		s = ''
		for i in A:
			d[i] += 1
			l.append(i)
			while l:
				if d[l[0]] > 1:
					l.pop(0)
				else:
					s += l[0]
					break
			if len(l) == 0:
				s += '#'
		return s


class Solution:

	def FirstNonRepeating(self, A):
		n = len(A)
		ans = ''
		q = []
		hmap = {}
		j = 0
		for i in range(n):
			if A[i] not in hmap:
				hmap[A[i]] = 1
			else:
				hmap[A[i]] += 1
			q.append(A[i])
			while j <= len(q) - 1 and hmap[q[j]] > 1:
				j += 1
			if j < len(q):
				ans += q[j]
			else:
				ans += '#'
		return ans


class Solution:

	def FirstNonRepeating(self, A):
		l = []
		mp = {}
		ans = ''
		for i in A:
			if i not in mp:
				l.append(i)
				mp[i] = 1
			elif i in l:
				l.remove(i)
			ans += l[0] if l else '#'
		return ans


class Solution:

	def FirstNonRepeating(self, s):
		d = dict()
		n = list()
		r = list()
		for ch in s:
			if d.get(ch):
				if ch in n:
					n.remove(ch)
			else:
				d[ch] = 1
				n.append(ch)
			if n:
				r.append(n[0])
			else:
				r.append('#')
		return ''.join(r)


class Solution:

	def FirstNonRepeating(self, A):
		dict = {}
		q = []
		ans = ''
		for i in A:
			dict[i] = dict.get(i, 0) + 1
			q.append(i)
			while len(q) != 0 and dict[q[0]] > 1:
				q.pop(0)
			if len(q) == 0:
				ans += '#'
			else:
				ans += q[0]
		return ans


from collections import deque, defaultdict

class Solution:

	def FirstNonRepeating(self, A):
		stream_queue = deque()
		char_count = defaultdict(int)
		result = ''
		for char in A:
			char_count[char] += 1
			if char_count[char] == 1:
				stream_queue.append(char)
			while stream_queue and char_count[stream_queue[0]] > 1:
				stream_queue.popleft()
			if not stream_queue:
				result += '#'
			else:
				result += stream_queue[0]
		return result


from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		ans = ''
		mp = {}
		q = deque()
		for i in range(len(A)):
			if A[i] not in mp:
				q.append(A[i])
			mp[A[i]] = mp.get(A[i], 0) + 1
			while len(q) > 0 and mp[q[0]] > 1:
				q.popleft()
			if len(q) > 0:
				ans += q[0]
			else:
				ans += '#'
		return ans


class Solution:

	def FirstNonRepeating(self, A):
		existing_char = dict()
		non_rep = list()
		result = list()
		for char in A:
			if existing_char.get(char):
				if char in non_rep:
					non_rep.remove(char)
			else:
				existing_char[char] = 1
				non_rep.append(char)
			if non_rep:
				result.append(non_rep[0])
			else:
				result.append('#')
		return ''.join(result)


class Solution:

	def FirstNonRepeating(self, A):
		list = []
		mp = {}
		ans = ''
		for ch in A:
			if ch not in mp:
				list.append(ch)
				mp[ch] = 1
			elif ch in list:
				list.remove(ch)
			ans += list[0] if list else '#'
		return ans


from collections import OrderedDict

class Solution:

	def FirstNonRepeating(self, A):
		d = OrderedDict()
		s = ''
		for i in A:
			if i not in d.keys():
				d[i] = 1
			else:
				d[i] = d.get(i) + 1
			b = False
			for (x, y) in d.items():
				if y == 1:
					s += x
					b = True
					break
			if b == False:
				s += '#'
		return s


class Solution:

	def FirstNonRepeating(self, A):
		freq = {}
		in_queue = set()
		result = ''
		queue = []
		for char in A:
			freq[char] = freq.get(char, 0) + 1
			if char in in_queue:
				in_queue.remove(char)
				queue.remove(char)
			elif freq[char] == 1:
				in_queue.add(char)
				queue.append(char)
			if not queue:
				result += '#'
			else:
				result += queue[0]
		return result


class Solution:

	def FirstNonRepeating(self, A):
		cnt = {}
		q = []
		ans = []
		for i in A:
			if i not in cnt:
				cnt[i] = 1
			else:
				cnt[i] += 1
			q.append(i)
			while q and cnt[q[0]] > 1:
				q.pop(0)
			ans.append(q[0] if q else '#')
		return ''.join(ans)


class Solution:

	def FirstNonRepeating(self, A):
		f = {}
		odr = []
		r = ''
		for i in A:
			f[i] = f.get(i, 0) + 1
			odr.append(i)
			while odr and f[odr[0]] > 1:
				odr.pop(0)
			if odr:
				r += odr[0]
			else:
				r += '#'
		return r


class Solution:

	def FirstNonRepeating(self, A):
		que = []
		has = {}
		new = ''
		for i in A:
			if len(que) == 0:
				if i not in has:
					que.append(i)
					new += que[0]
				else:
					new += '#'
			elif i in que:
				has[i] = 0
				que.remove(i)
				if len(que) == 0:
					new += '#'
				else:
					new += que[0]
			elif i in has:
				if len(que) == 0:
					new += '#'
				else:
					new += que[0]
			else:
				que.append(i)
				new += que[0]
		return new


from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		q = deque()
		v = [0] * 26
		v1 = [0] * 26
		a = []
		for i in range(len(A)):
			t = A[i]
			x = ord(t) - 97
			if v[x] == 0:
				q.append(t)
				v[x] = 1
			elif v1[x] == 0:
				q.remove(t)
				v1[x] = 1
			if len(q) == 0:
				a.append('#')
			else:
				a.append(q[0])
		return ''.join(a)


from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		freq = {}
		queue = deque()
		result = ''
		for ch in A:
			freq[ch] = freq.get(ch, 0) + 1
			if freq[ch] == 1:
				queue.append(ch)
			elif freq[ch] > 1 and ch in queue:
				queue.remove(ch)
			if len(queue) == 0:
				result += '#'
			else:
				result += queue[0]
		return result


class Solution:

	def FirstNonRepeating(self, A):
		existing = dict()
		non_repeat = list()
		res = list()
		for i in A:
			if existing.get(i):
				if i in non_repeat:
					non_repeat.remove(i)
			else:
				existing[i] = 1
				non_repeat.append(i)
			if non_repeat:
				res.append(non_repeat[0])
			else:
				res.append('#')
		return ''.join(res)


class Solution:

	def FirstNonRepeating(self, A):
		d = {}
		q = []
		s = ''
		for i in A:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
			q.append(i)
			while len(q) != 0:
				if d[q[0]] > 1:
					q.remove(q[0])
				else:
					s = s + q[0]
					break
			else:
				s = s + '#'
		return s


class Solution:

	def FirstNonRepeating(self, A):
		ans = ''
		st = []
		m = {}
		for i in A:
			m[i] = 1 + m.get(i, 0)
			st.append(i)
			while st:
				if m[st[0]] > 1:
					st.pop(0)
				else:
					ans += st[0]
					break
			if not st:
				ans += '#'
		return ans


from collections import OrderedDict

class Solution:

	def FirstNonRepeating(self, A):
		d = OrderedDict()
		s = ''
		for i in A:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
			for j in d:
				if d[j] == 1:
					s += j
					break
			else:
				s += '#'
		return s


from queue import Queue

def solve(str):
	freq = [0] * 26
	q = Queue()
	ans = ''
	for ch in str:
		freq[ord(ch) - ord('a')] += 1
		q.put(ch)
		while not q.empty():
			if freq[ord(q.queue[0]) - ord('a')] > 1:
				q.get()
			else:
				ans += q.queue[0]
				break
		if q.empty():
			ans += '#'
	return ans

class Solution:

	def FirstNonRepeating(self, A):
		return solve(A)


class Solution:

	def FirstNonRepeating(self, A):
		queue = []
		dict = {}
		res = ''
		for c in A:
			if dict.get(c) is None:
				dict[c] = True
				queue.append(c)
				if queue:
					res += queue[0]
				else:
					res += '#'
			else:
				if c in queue:
					queue.remove(c)
				if queue:
					res += queue[0]
				else:
					res += '#'
		return res


class Solution:

	def FirstNonRepeating(self, A):
		l = []
		f = {}
		s = ''
		for i in A:
			if i not in f:
				l.append(i)
				f[i] = 1
			elif i in l:
				l.remove(i)
			if l:
				s += l[0]
			else:
				s += '#'
		return s


class Solution:

	def FirstNonRepeating(self, A):
		res = ''
		alp = [0] * 26
		ptr = 0
		for i in range(len(A)):
			alp[ord(A[i]) - ord('a')] += 1
			while ptr <= i and alp[ord(A[ptr]) - ord('a')] != 1:
				ptr += 1
			if ptr > i:
				res += '#'
			else:
				res += A[ptr]
		return res


class Solution:

	def FirstNonRepeating(self, A):
		m = dict()
		s = []
		ans = ''
		for i in range(len(A)):
			ch = A[i]
			if ch in m:
				m[ch] += 1
			else:
				m[ch] = 1
			s.append(ch)
			while len(s) != 0:
				if m[s[0]] > 1:
					s.pop(0)
				else:
					ans += s[0]
					break
			if len(s) == 0:
				ans += '#'
		return ans


from collections import defaultdict
from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		hmap = defaultdict(int)
		queue = deque()
		ans = ''
		for i in A:
			hmap[i] += 1
			queue.append(i)
			a = '#'
			while queue and hmap[queue[0]] != 1:
				queue.popleft()
			if queue:
				a = queue[0]
			ans += a
		return ans


class Solution:

	def FirstNonRepeating(self, A):
		arr = [0] * 26
		qu = []
		ans = ''
		for i in range(0, len(A)):
			arr[ord(A[i]) - ord('a')] += 1
			if arr[ord(A[i]) - ord('a')] == 1:
				qu.append(A[i])
			w = 0
			while len(qu) != 0:
				if arr[ord(qu[0]) - ord('a')] > 1:
					qu.pop(0)
				else:
					ans = ans + qu[0]
					w = 1
					break
			if w == 0:
				ans = ans + '#'
		return ans


from collections import deque

class Solution:

	def FirstNonRepeating(self, A):
		result = []
		hashmap = {}
		queue = deque()
		for i in range(0, len(A)):
			if A[i] not in hashmap:
				hashmap[A[i]] = 1
			else:
				hashmap[A[i]] = hashmap[A[i]] + 1
			queue.append(A[i])
			while queue:
				if hashmap[queue[0]] > 1:
					queue.popleft()
				else:
					result.append(queue[0])
					break
			if not queue:
				result.append('#')
		return ''.join(result)


class Solution:

	def FirstNonRepeating(self, A):
		letter_dict = dict()
		output = ''
		for i in range(len(A)):
			if A[i] in letter_dict:
				count = letter_dict[A[i]][1]
				letter_dict[A[i]] = [i, count + 1]
			else:
				letter_dict[A[i]] = [i, 1]
			lowest_pos = 10 ** 5
			lowest_letter = '#'
			for letter in letter_dict:
				if letter_dict[letter][1] == 1:
					if lowest_pos > letter_dict[letter][0]:
						lowest_pos = letter_dict[letter][0]
						lowest_letter = letter
			output = output + lowest_letter
		return output


class Solution:

	def FirstNonRepeating(self, l):
		s = ''
		a = []
		c = dict()
		c['55'] = 0
		for i in range(len(l)):
			if l[i] in c:
				c[l[i]] = c[l[i]] + 1
			else:
				c[l[i]] = 1
			if c[l[i]] == 1:
				a.append(l[i])
			if len(a) == 0:
				s += '#'
			elif c[a[0]] == 1:
				s += a[0]
			else:
				while len(a) != 0 and c[a[0]] != 1:
					a.pop(0)
				if len(a) == 0:
					s += '#'
				else:
					s += a[0]
		return s


from collections import OrderedDict

class Solution:

	def calc(self, word):
		n = len(word)
		return '#'

	def FirstNonRepeating(self, A):
		N = len(A)
		dic = OrderedDict()
		res = ''
		word = ''
		for i in range(N):
			st = False
			word += A[i]
			if A[i] not in dic:
				dic[A[i]] = 1
			else:
				dic[A[i]] += 1
			for (s, q) in dic.items():
				if q == 1:
					res += str(s)
					st = True
					break
			if st == False:
				res += '#'
		return res


class Solution:

	def FirstNonRepeating(self, A):
		ch = 0
		res = ''
		for i in range(len(A)):
			s = A[:i + 1]
			f = True
			for _ in range(ch, i + 1):
				if s.find(A[ch], 0, ch) == -1 and s.find(A[ch], ch + 1) == -1:
					res += A[ch]
					f = False
					break
				ch = ch + 1
			if f:
				res += '#'
		return res


class Solution:

	def FirstNonRepeating(self, A):
		if len(A) == 0 or len(A) == 1:
			return A
		t = set()
		l = []
		ans = ''
		for i in A:
			if i in t:
				if i in l:
					l.remove(i)
			else:
				t.add(i)
				l.append(i)
			if len(l) > 0:
				ans = ans + l[0]
			else:
				ans = ans + '#'
		return ans


class Solution:

	def FirstNonRepeating(self, A):
		if len(A) == 0 or len(A) == 1:
			return A
		setA = set()
		listA = []
		ans = ''
		for i in A:
			if i in setA:
				if i in listA:
					listA.remove(i)
			else:
				setA.add(i)
				listA.append(i)
			if len(listA) > 0:
				ans = ans + listA[0]
			else:
				ans = ans + '#'
		return ans


from queue import Queue

class Solution:

	def FirstNonRepeating(self, A):
		freq = [0] * 26
		q = Queue()
		ans = ''
		for i in range(len(A)):
			q.put(A[i])
			freq[ord(A[i]) - ord('a')] += 1
			while not q.empty():
				if freq[ord(q.queue[0]) - ord('a')] > 1:
					q.get()
				else:
					ans += q.queue[0]
					break
			if q.empty():
				ans += '#'
		return ans


class Solution:

	def FirstNonRepeating(self, A):
		freq = [0] * 26
		res = ''
		queue = []
		for i in range(len(A)):
			c = A[i]
			freq[ord(c) - 97] += 1
			if freq[ord(c) - 97] == 1:
				queue.append(c)
			else:
				while queue and freq[ord(queue[0]) - 97] > 1:
					queue.pop(0)
			if queue:
				res += queue[0]
			else:
				res += '#'
		return res