Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

First non-repeating in a stream

Medium Acceptance 31.65% Points 30.00

You are given an input stream s consisting of lowercase alphabets. As you read characters from the stream one by one, determine which character has appeared only once in the stream up to that point. If multiple characters have appeared only once, identify the first one that appeared. If no such character exists, append # to the result. Your task is to build a string that represents the character status for each point in the stream.

NOTE:

  1. You must determine the result for each index i in the stream, where 0=i<n.
  2. To compute the result for each index i, consider the substring starting from the first character up to the i-th character in the stream.
Examples
Example 1

Example 1

Input: s = "abac"

Output: "aabb"

Explanation: At position 0: 'a' is non-repeating. At position 1: 'a' and 'b' are non-repeating, with 'a' appearing first. At position 2: 'b' is now the first non-repeating character as 'a' repeats. At position 3: 'b' remains the first non-repeating character.

Example 2

Example 2

Input: s = "aabbcc"

Output: "a#b#c#"

Explanation: At second , fourth and sixth position a, b, and c repeats respectively.

Hints
Hint 1
Expected Time Complexity: O(n)
Hint 2
Expected Auxiliary Space: O(n)
Constraints
  • 1 <= s.size()<= 10^5
  • 'a' <= s[i] <= 'z'
Companies
Amazon Microsoft Adobe Yahoo Flipkart
Topics
Queue
Solution.cs C#JavaPythonC++Javascript

Unlock the code editor

Sign in to write, run, and submit your solution against the full test suite.

  • Run code against sample & hidden test cases
  • Save submissions and track your streak
  • Compare with editorial & community solutions