PythonMediumHashing20 min

Find the first non-repeated character

The input contains lowercase English letters only. Preserve the original order when choosing the result. Interviewers use this problem to assess count first, then scan the original order.

Input

One line of lowercase letters, possibly empty.

Output

Print the result on one line; print an empty line for an empty string.

Constraints

0 <= length <= 100000.

Example

Input

swiss

Output

Example 2 input

abacbd

Output

The first unique character need not be first overall.

Public test cases (2)

Input
```
swiss
```
Expected output
```
w
```
Input
```
aabb
```
Expected output
```
NONE
```

Hints (2)

Identify the state needed to avoid repeated work.
Count first, then scan the original order.

Target complexity: time O(n) · space O(1), since there are only 26 letters

Your solution

import sys


def solve_first_non_repeated_character(s):
    # your code
    return "NONE"


if __name__ == "__main__":
    data = sys.stdin.read()
    s = data.split("\n", 1)[0]
    result = solve_first_non_repeated_character(s)
    print(result)

Standard input

Checking runner availability…

Reference solution

Check whether a number is prime · Easy
Check whether a string is a palindrome · Easy
Check whether two strings are anagrams · Easy
Compute the factorial of a number · Easy
Count vowels and consonants · Easy
Find the first occurrence with binary search · Easy
Find the missing number from zero through n · Easy
Find the second largest distinct value · Easy
Generate the Fibonacci series · Easy
Remove duplicate values while preserving order · Easy

All Python programs

Find the first non-repeated character

Input

Output

Constraints

Example

Public test cases (2)

Your solution

Reference solution

More Python programs