Katkat
Back

Find first non-repeating character

Walmart LabsMachine Learning Engineer · Onsite
EasyMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use hash maps or frequency arrays to achieve optimal time complexity when processing character streams or strings.

Problem Statement

Given a string s consisting of lowercase English letters, write a function that finds the first non-repeating character in the string and returns its index. If it does not exist, return -1.

Function Signature

def first_unique_char(s: str) -> int:

Constraints

  • 1 <= len(s) <= 10^5
  • s consists only of lowercase English letters.

Examples

Example 1:

  • Input: s = "leetcode"
  • Output: 0
  • Explanation: The character 'l' at index 0 is the first character that does not repeat.

Example 2:

  • Input: s = "loveleetcode"
  • Output: 2
  • Explanation: 'l' repeats, 'o' repeats, but 'v' at index 2 is the first character that appears only once.

Example 3:

  • Input: s = "aabb"
  • Output: -1
  • Explanation: Every character repeats.

Edge Cases

  • Single character strings.
  • Strings where all characters repeat.
  • Very long strings (up to 10^5 characters).

Hints

Hint 1

Consider using a frequency map to store the count of each character encountered in the string.

Hint 2

A two-pass approach is often more efficient: first count the frequencies, then iterate through the string a second time to find the first character with a count of 1.

Hint 3

Since the input is restricted to lowercase English letters, an array of size 26 can be used instead of a hash map to improve performance.

Follow-up questions

  • How would you modify your solution if the input string was a massive stream of characters rather than a stored string?
  • What is the space complexity of your solution, and can it be improved?
  • How would you handle the requirement if the input included Unicode characters instead of just lowercase English letters?