First Unique Character Solution for Capgemini

Company: Capgemini · Difficulty: Easy · Topics: String, Hash Table

Problem Statement

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

Examples

Example 1:

Input: s = "leetcode"

Output: 0

Explanation: The first non-repeating character is 'l' at index 0.

Example 2:

Input: s = "loveleetcode"

Output: 2

Explanation: The first non-repeating character is 'v' at index 2.

Example 3:

Input: s = "aabb"

Output: -1

Explanation: All characters repeat, so return -1.

Example 4:

Input: s = "a"

Output: 0

Explanation: Single character is always unique.

Intuition

The key insight is to use a hash table (or array) to count the frequency of each character, then scan the string again to find the first character with frequency 1.

This approach requires two passes:

1. First pass: Count frequency of each character

2. Second pass: Find first character with count = 1

Approach

Approach 1: Hash Table with Two Passes (Optimal)

1. Create a frequency array of size 26 (for lowercase letters) or 128 (for ASCII)

2. First pass: Count frequency of each character

3. Second pass: Find first character with frequency = 1

4. Return the index or -1 if not found

Approach 2: Hash Table with Single Pass

1. Use a hash table to store character and its first occurrence

2. Use another hash table to track frequency

3. Scan once and maintain both maps

4. Find minimum index among characters with frequency = 1

Approach 3: Brute Force

1. For each character, check if it appears again in the string

2. Return the first character that doesn't repeat

Dry Run

Let's trace through Example 1: s = "leetcode"

Hash Table Approach:

• Frequency array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
• First pass: count frequencies
• 'l': freq[11] = 1
• 'e': freq[4] = 1
• 'e': freq[4] = 2
• 't': freq[19] = 1
• 'c': freq[2] = 1
• 'o': freq[14] = 1
• 'd': freq[3] = 1
• 'e': freq[4] = 3
• Second pass: find first with freq = 1
• s[0] = 'l', freq[11] = 1 ✓ (return 0)

Key Insights

1. Two Passes: First count, then find

2. Hash Table: Efficient frequency counting

3. Order Matters: Must scan in original order to find "first" unique

4. Edge Cases: Handle empty string, single character, all repeating

Edge Cases

1. Empty string: Return -1

2. Single character: Return 0

3. All repeating: Return -1

4. Case sensitivity: Usually lowercase letters only

More Capgemini coding questions