-
Notifications
You must be signed in to change notification settings - Fork 0
/
firstNonRepeatingCharacter.py
66 lines (64 loc) · 2.16 KB
/
firstNonRepeatingCharacter.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Problem Description:
# Given a string A denoting a stream of lowercase alphabets, you have to make a new string B. B
# is formed such that we have to find the first non-repeating character each time a character is inserted to the
# stream and append it at the end to B. If no non-repeating character is found, append '#' at the end of B.
#
# Problem Constraints
# 1 <= |A| <= 100000
#
# Input Format
# The only argument given is string A.
#
# Output Format
# Return a string B after processing the stream of lowercase alphabets A.
#
# Example Input
# Input 1: A = "abadbc"
# Input 2: A = "abcabc"
#
# Example Output
# Output 1: "aabbdd"
# Output 2: "aaabc#"
#
# Example Explanation
# Explanation 1:-
# "a" - first non repeating character 'a'
# "ab" - first non repeating character 'a'
# "aba" - first non repeating character 'b'
# "abad" - first non repeating character 'b'
# "abadb" - first non repeating character 'd'
# "abadbc" - first non repeating character 'd'
#
# Explanation 2:-
# "a" - first non repeating character 'a'
# "ab" - first non repeating character 'a'
# "abc" - first non repeating character 'a'
# "abca" - first non repeating character 'b'
# "abcab" - first non repeating character 'c'
# "abcabc" - no non repeating character so '#'
class Solution:
# @param A : string
# @return a strings
def solve(self, A):
queue = []
hmap = {} # stores the frequency of each character
ans = ""
for val in A:
if val not in hmap.keys():
# if value is unique
hmap[val] = 1
queue.append(val)
else:
# if value is repeated
hmap[val] += 1
while queue and hmap[queue[0]] > 1:
queue.pop(0)
if queue:
ans += queue[0]
else:
ans += "#"
return ans
# Solution Approach:-
# We need to maintain a map for each character of the stream.
# After that, We can also maintain a queue for the extraction of information.
# Each character is inserted and removed from the queue at most once; hence time complexity is O(n).