Find index of first unique character

Given a string s, return the index of the first character that appears exactly once; if none exists, return -1. Assume s may include both lowercase and uppercase English letters. Clarify whether the check is case-sensitive and implement both case-sensitive and case-insensitive variants. Follow-ups: (1) Optimize for a small fixed alphabet—can you use constant extra space? (2) How would you support full Unicode, including grapheme clusters and normalization issues? (3) If s arrives as a stream too large for memory, how would you detect the first unique character online? Analyze time and space complexity.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Find Index of First Unique Character

Given a string s, return the index of the first character that appears exactly once in s. If no such character exists, return -1.

The string may include both lowercase and uppercase English letters. For this challenge the check is case-sensitive, so 'a' and 'A' are treated as different characters.

Examples:

• s = "leetcode" -> 0 (the first 'l' is the first character that appears exactly once)
• s = "loveleetcode" -> 2 (the 'v' at index 2 is the first unique character)
• s = "aabb" -> -1 (no character appears exactly once)

Follow-ups to discuss (no code required):

1. For a small fixed alphabet (e.g. 52 ASCII letters), can you achieve O(1) extra space?
2. How would you extend this to full Unicode, accounting for grapheme clusters and normalization (NFC/NFD)?
3. If s arrives as a stream too large to fit in memory, how would you detect the first unique character online?

Constraints

• 1 <= len(s) <= 10^5 (an empty string returns -1)
• s consists of lowercase and uppercase English letters
• The check is case-sensitive: 'a' and 'A' are distinct

Hints

1. First count how many times each character occurs. A hash map (or a fixed-size array indexed by character) works well.
2. After counting, scan the string left to right and return the index of the first character whose count is exactly 1.
3. Two linear passes give O(n) time. For a fixed alphabet, the count storage is O(1) extra space.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given a string s, return the index of the first character that appears exactly once; if none exists, return -1. Assume s may include both lowercase and uppercase English letters. Clarify whether the check is case-sensitive and implement both case-sensitive and case-insensitive variants. Follow-ups: ( 1) Optimize for a small fixed alphabet—can you use constant extra space? ( 2) How would you support full Unicode, including grapheme clusters and normalization issues? ( 3) If s arrives as a stream too large for memory, how would you detect the first unique character online? Analyze time and space complexity.

Recommended Approach

Scan the string once to count each character, then scan the original string again and return the first index whose count is 1. This preserves original order and is O(n). A sorting-based approach can group equal characters but loses original order unless it stores indices, and it is typically O(n log n).

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Time: O(n). Space: O(k), where k is the character alphabet size, or O(n) in the worst case for arbitrary Unicode.

Edge Cases and Tests

Empty string, all repeated characters, first character unique, last character unique, case-sensitive input such as "aA", and alphanumeric characters.