First non-repeating character in a string

Given a string, the task is to find the first non-repeating character in it. If all characters are repeating or the string is empty, the function should return a special indicator (e.g., None or -1).

Input-Output Examples

Example 1:

Input: "swiss"
Output: 'w' (The first non-repeating character is 'w')

Example 2:

Input: "programming"
Output: 'p' (The first non-repeating character is 'p')

Example 3:

Input: "aabbcc"
Output: None (All characters are repeating)

Example 4:

Input: ""
Output: None (Empty string)

Approach:

To find the first non-repeating character, we can use a hash map to store the frequency of each character in the string. By doing so, we can efficiently determine which characters are non-repeating.

Steps to implement:

Traverse the string and count the frequency of each character using a hash map.
Traverse the string a second time to find the first character with a frequency of one.
If no such character is found, return None.

Technique to be used: Hash map for character frequency counting

C++ Program to find first non-repeating character in a string

cpp

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

char firstNonRepeatingCharacter(string str) {
    unordered_map<char, int> charCount;
    
    // Count frequency of each character
    for (char c : str) {
        charCount[c]++;
    }
    
    // Find the first non-repeating character
    for (char c : str) {
        if (charCount[c] == 1) {
            return c;
        }
    }
    
    return '\0'; // Return null character if no non-repeating character is found
}

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

Java Program to find first non-repeating character in a string

java

import java.util.HashMap;
import java.util.Map;

public class FirstNonRepeatingCharacter {
    public static Character firstNonRepeatingCharacter(String str) {
        Map<Character, Integer> charCount = new HashMap<>();
        
        // Count frequency of each character
        for (char c : str.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }
        
        // Find the first non-repeating character
        for (char c : str.toCharArray()) {
            if (charCount.get(c) == 1) {
                return c;
            }
        }
        
        return null; // Return null if no non-repeating character is found
    }

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

Python Program to find first non-repeating character in a string

python

def first_non_repeating_character(string):
    char_count = {}
    
    # Count frequency of each character
    for char in string:
        char_count[char] = char_count.get(char, 0) + 1
    
    # Find the first non-repeating character
    for char in string:
        if char_count[char] == 1:
            return char
    
    return None

# Example usage
string = "swiss"
result = first_non_repeating_character(string)
if result:
    print("The first non-repeating character is:", result)
else:
    print("No non-repeating character found.")

Related Articles