Frontend School

Track First Unique Character

DSA
easy

Track First Unique Character

Easy
Queue
Hash Map
String

Overview

Imagine building a real-time analytics dashboard that needs to identify the first unique character in a continuously incoming stream of data. This is crucial for various applications like anomaly detection, data processing, or even simple text analysis.

This problem challenges you to simulate this process, tracking the first character that has appeared exactly once, as new characters arrive in a stream.

What you need to do / Task

Implement the function trackFirstUniqueChar that takes a string s representing a stream of characters. For each character processed in the stream (from left to right), you must:

  1. Determine the first character that has appeared exactly once in the stream up to that point.
  2. Collect these determined characters into an array.
  3. If, at any point, no character has appeared exactly once in the processed substring, record '#' for that position.

Input & output

  • Input: s: A string consisting of lowercase English letters.
  • Output: An array of characters (strings of length 1). output[i] should be the first unique character in s[0...i], or '#' if none exists.

Clarifications

  • Empty input: If s is an empty string, return an empty array.
  • Character set: Assume s consists only of lowercase English letters ('a'-'z').
  • Uniqueness: A character is unique if its total count in the processed substring s[0...i] is exactly one.

Examples

1

Example 1

Input:

s = "abaccd"

Output:

["a", "a", "b", "b", "b", "b"]

Note:

  1. 'a': 'a' is unique. Result: ['a']
  2. 'b': 'a' is unique. Result: ['a', 'a']
  3. 'a': 'a' is now repeated. 'b' is unique. Result: ['a', 'a', 'b']
  4. 'c': 'b' is unique. Result: ['a', 'a', 'b', 'b']
  5. 'c': 'c' is now repeated. 'b' is unique. Result: ['a', 'a', 'b', 'b', 'b']
  6. 'd': 'b' is unique. Result: ['a', 'a', 'b', 'b', 'b', 'b']
2

Example 2

Input:

s = "aabbc"

Output:

["a", "#", "b", "#", "c"]

Note:

  1. 'a': 'a' is unique. Result: ['a']
  2. 'a': 'a' is repeated. No unique character. Result: ['a', '#']
  3. 'b': 'b' is unique. Result: ['a', '#', 'b']
  4. 'b': 'b' is repeated. No unique character. Result: ['a', '#', 'b', '#']
  5. 'c': 'c' is unique. Result: ['a', '#', 'b', '#', 'c']

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters.

Out of scope

  • Optimization for extremely large alphabets (e.g., Unicode characters) is not required; focus on the given constraints.
  • Error handling for invalid input types is not necessary.

What interviewers evaluate

  • Correctness of the algorithm for tracking unique characters using appropriate data structures.
  • Efficiency of the solution in terms of time and space complexity.
  • Clarity and readability of the code.
  • Ability to handle edge cases like no unique characters or empty input.

Loading editor...