Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

First non-repeating in a stream

Medium Acceptance 31.65% Points 30

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.

Constraints
  • 1 <= s.size()<= 10^5
  • 'a' <= s[i] <= 'z'
Hints
  • Expected Time Complexity: O(n)
  • Expected Auxiliary Space: O(n)
Topics
Queue
Companies
Amazon Microsoft Adobe Yahoo Flipkart
Added 13 May 2025 31.65% acceptance
Ln 1, Col 1Sign in to save your code
abac
aabb