How do you find the first non-repeating character?

Finding the first non-repeating character in a string is a common problem that can be approached in various ways. The goal is to identify the first character in the string that does not repeat, and this can be achieved efficiently using different algorithms. Below, I will outline a few methods, their implementations, best practices, and common pitfalls to avoid.

Approach 1: Using a Hash Map

One of the most efficient ways to solve this problem is by using a hash map (or an object in JavaScript) to store the count of each character. This approach runs in O(n) time complexity, where n is the length of the string.

function firstNonRepeatingCharacter(str) {
    const charCount = {};
    
    // Count occurrences of each character
    for (let char of str) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    
    // Find the first non-repeating character
    for (let char of str) {
        if (charCount[char] === 1) {
            return char;
        }
    }
    
    return null; // Return null if no non-repeating character is found
}

Example

For the input string "swiss", the function would return 'w' as it is the first character that does not repeat.

Approach 2: Using an Array

Another method is to use an array to keep track of the counts. This is particularly useful when the character set is limited (like lowercase English letters).

function firstNonRepeatingCharacter(str) {
    const charCount = new Array(26).fill(0);
    
    // Count occurrences of each character
    for (let char of str) {
        charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    // Find the first non-repeating character
    for (let char of str) {
        if (charCount[char.charCodeAt(0) - 'a'.charCodeAt(0)] === 1) {
            return char;
        }
    }
    
    return null; // Return null if no non-repeating character is found
}

Example

In the string "leetcode", the function would return 'l' as it is the first non-repeating character.

Best Practices

• Always consider edge cases, such as an empty string or a string with all repeating characters.
• Choose the right data structure based on the input size and character set.
• Keep the code clean and well-commented for better readability and maintainability.

Common Mistakes

• Not accounting for case sensitivity (e.g., treating 'A' and 'a' as the same character).
• Overlooking the possibility of an empty input string.
• Using inefficient algorithms that lead to O(n^2) time complexity, such as nested loops.

In conclusion, finding the first non-repeating character can be efficiently solved using hash maps or arrays, depending on the constraints of the problem. By following best practices and avoiding common mistakes, you can implement a robust solution that performs well across various scenarios.