Find the First Non-Repeating Character

(Coding Clutch Challenge Series 101) – Coding Challenge #2

Have you ever had to find the odd one out in a group? The “First Non-Repeating Character” challenge is just like that, but for strings. This problem tests your understanding of string manipulation and data structure usage.

Coding Clutch Challenge Series 101 – All Coding Challenges

Let’s explore how to solve it step-by-step!

Understanding the Problem

Problem Statement

You are given a string. Your task is to find the first character that doesn’t repeat. If all characters repeat, return None.

Input-Output Examples

• Input: "swiss" → Output: 'w'
• Input: "programming" → Output: 'p'
• Input: "aabbcc" → Output: None

Constraints and Edge Cases

• The string contains only lowercase English letters.
• Consider empty strings and strings with only one character.
• Handle cases where no unique characters exist.

Approach to the Solution

Frequency Counting with Data Structures

Using a dictionary or hash map, count the frequency of each character and identify the first one with a frequency of 1.

Index Tracking for Optimization

Use a combination of an array and a hash map to track indices and counts for faster lookups.

Alternative Approach Without Extra Space

Iterate through the string twice: once to count frequencies and another to find the first unique character.

Coding Clutch Challenge Series 101 – All Coding Challenges

Implementing Solutions in Multiple Languages

Python Implementation

def first_non_repeating_char(s):
    frequency = {}
    for char in s:
        frequency[char] = frequency.get(char, 0) + 1
    for char in s:
        if frequency[char] == 1:
            return char
    return None

# Example
print(first_non_repeating_char("swiss"))  # Output: 'w'

Explanation:

• Count frequencies using a dictionary.
• Traverse the string again to find the first character with a frequency of 1.

C Implementation

#include <stdio.h>
#include <string.h>

char firstNonRepeatingChar(const char* str) {
    int count[26] = {0};
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        count[str[i] - 'a']++;
    }
    for (int i = 0; i < len; i++) {
        if (count[str[i] - 'a'] == 1) {
            return str[i];
        }
    }
    return '\0';
}

int main() {
    const char* str = "swiss";
    char result = firstNonRepeatingChar(str);
    if (result) {
        printf("First non-repeating character: %c\n", result);
    } else {
        printf("No non-repeating character found.\n");
    }
    return 0;
}

Output:
First non-repeating character: w

C++ Implementation

#include <iostream>
#include <unordered_map>
using namespace std;

char firstNonRepeatingChar(string str) {
    unordered_map<char, int> frequency;
    for (char c : str) {
        frequency[c]++;
    }
    for (char c : str) {
        if (frequency[c] == 1) {
            return c;
        }
    }
    return '\0';
}

int main() {
    string str = "swiss";
    char result = firstNonRepeatingChar(str);
    if (result) {
        cout << "First non-repeating character: " << result << endl;
    } else {
        cout << "No non-repeating character found." << endl;
    }
    return 0;
}

Output:
First non-repeating character: w

Java Implementation

import java.util.LinkedHashMap;
import java.util.Map;

public class Main {
    public static Character firstNonRepeatingChar(String str) {
        Map<Character, Integer> frequency = new LinkedHashMap<>();
        for (char c : str.toCharArray()) {
            frequency.put(c, frequency.getOrDefault(c, 0) + 1);
        }
        for (char c : str.toCharArray()) {
            if (frequency.get(c) == 1) {
                return c;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        String str = "swiss";
        Character result = firstNonRepeatingChar(str);
        if (result != null) {
            System.out.println("First non-repeating character: " + result);
        } else {
            System.out.println("No non-repeating character found.");
        }
    }
}

Output:
First non-repeating character: w

Coding Clutch Challenge Series 101 – All Coding Challenges

Optimized Methods

Efficient Solution for Large Strings

Use a single-pass solution with a queue to minimize space usage.

Time and Space Complexity

• Frequency Count: O(n) time, O(n) space.
• Double Loop (No Extra Space): O(n^2) time, O(1) space.

Debugging Tips

1. Ensure edge cases like empty strings are handled properly.
2. Watch out for string index out-of-bounds errors.
3. Check if your frequency map is initialized correctly.

Coding Clutch Challenge Series 101 – All Coding Challenges

FAQs

1. Can this problem be solved using recursion?
   It’s possible but not recommended due to increased complexity.
2. What happens with non-alphabetic characters?
   Extend the frequency map to include all ASCII characters.
3. How do different languages handle edge cases?
   Python and Java handle empty inputs gracefully, but ensure to handle them explicitly in C and C++.
4. Why is the problem time-sensitive in real applications?
   Large data sets require optimized solutions to maintain performance.
5. What are other similar problems to practice?
   Problems like “Find the Most Frequent Character” or “Longest Substring Without Repeating Characters” are great follow-ups.

Coding Clutch Challenge Series 101 – All Coding Challenges