122. First Non Repeated Character in a Stream

First Non Repeated Character in a Stream

Design a class that finds the first non-repeated character in a string.

The full string is not given at once. Instead, small substrings are streamed in the order they appear in the larger string.

After processing streamed substrings, return the first character whose total frequency in the full streamed string is exactly 1.

The character space can include any character, such as lowercase letters, uppercase letters, digits, spaces, punctuation, and symbols.

The streamed substrings must be processed in arrival order, and together they form the full string.
Assume the full string is too large to fit into RAM on a single machine.

If no non-repeated character exists, return an empty string "".

Methods

FirstNonRepeatedCharacter()

Initializes an empty streamed string.

void appendChunk(String chunk)

chunk.length() ≥ 1
Appends the streamed substring chunk to the end of the current string.
chunk may contain any characters.

String firstNonRepeatedCharacter()

Returns the first character whose frequency in the full streamed string is exactly 1.
Returns that character as a string of length 1.
Returns "" if no such character exists.

Rules

The final string is the concatenation of all streamed substrings in the exact order they are received.
The answer is based on the full string formed so far.
A character is non-repeated only if its total frequency is exactly 1.
The returned character must be the earliest such character by position in the streamed string.

Constraints

1 ≤ chunk.length() ≤ 10^4
The total number of calls to appendChunk and firstNonRepeatedCharacter is at most 10^5.
Characters may come from any valid character set representable in a String.
Input will not contain strings with unicode characters like emoji which are represented by two UTF-16 code units.
The solution should support incremental processing and must not assume the full string is available in one input.

Examples

Example 1

FirstNonRepeatedCharacter stream = new FirstNonRepeatedCharacter()
Output: ""

stream.appendChunk(chunk = "sw")
Output: ""

stream.appendChunk(chunk = "iss")
Output: ""

stream.firstNonRepeatedCharacter()
Output: w

Explanation:
The full streamed string is "swiss".
Frequencies are: s = 3, w = 1, i = 1.
The first non-repeated character is "w".

Example 2

FirstNonRepeatedCharacter stream = new FirstNonRepeatedCharacter()
Output: ""

stream.appendChunk(chunk = "aab")
Output: ""

stream.appendChunk(chunk = "ccbd")
Output: ""

stream.firstNonRepeatedCharacter()
Output: d

Explanation:
The full streamed string is "aabccbd".
Characters a, b, and c are repeated.
The first non-repeated character is "d".

Example 3

FirstNonRepeatedCharacter stream = new FirstNonRepeatedCharacter()
Output: ""

stream.appendChunk(chunk = "!!")
Output: ""

stream.appendChunk(chunk = "@@")
Output: ""

stream.firstNonRepeatedCharacter()
Output: ""

Explanation:
The full streamed string is "!!@@".
Every character is repeated, so the answer is "".

Example 4

FirstNonRepeatedCharacter stream = new FirstNonRepeatedCharacter()
Output: ""

stream.appendChunk(chunk = "a ")
Output: ""

stream.appendChunk(chunk = "a#")
Output: ""

stream.firstNonRepeatedCharacter()
Output: " "

Explanation:
The full streamed string is "a a#".
The character "a" is repeated.
The space character appears once and is the first non-repeated character.