Find the First Non-Repeating Character

mediumSave

CountingHash TableString

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Example 1

Input

[
  "leetcode"
]

Output

Explanation. The character 'l' is the first non-repeating character, and it is at index 0.

Example 2

Input

[
  "loveleetcode"
]

Output

Explanation. The characters 'l' and 'o' repeat. The character 'v' is the first non-repeating character, and it is at index 2.

Example 3

Input

[
  "aabb"
]

Output

-1

Explanation. All characters ('a' and 'b') repeat, so there is no non-repeating character.

Example 4

Input

[
  "z"
]

Output

Explanation. The character 'z' is the only character and it does not repeat, so it's at index 0.

Example 5

Input

[
  ""
]

Output

-1

Explanation. An empty string contains no characters, thus no non-repeating character.

Example 6

Input

[
  "ccbbaaffggd"
]

Output

Explanation. All characters except 'd' repeat. 'd' is at index 10 and is the first non-repeating character.

Follow-up: Can you solve this problem in a single pass? What if the string can contain uppercase letters, numbers, or special characters? How would your approach adapt?

Constraints:

The input string `s` consists only of lowercase English letters. The length of `s` is between 0 and 10^5.

Views: 4