String: Program to find the first non-repeating character in string

Write a program to find the first non-repeating character in a given string

A character is said to be non-repeating if that character occurs only once in the entire string
E.g. string "green"
the count of character g, r and n in the string “green” is 1, which are non-repeating characters of the string
and the first non-repeating character will be 'g'

Approach

• Find the count of occurrence of each character in a string and store it in a map called charCount
• Iiterate through the string and check the count of character using the above map.
• The first character that has the count 1 is the answer we are looking for.

If no character has count 1 then return # which denotes that no non-repeating character is present in the given string

Algorithm

1. Create a key-value pair hashmap named charCount to store the count of each char
2. Iterate through the given string character by character:
3. Check if the character is present in the charCount hashmap:
   • If present: Increment value of charCount for the character by one
   • If not present: Make the value of charCount for the character equal to 1
4. Iterate through the string character by character:
5. If the current char count = 1 then return character and exit
6. Return '#' if no character has count 1

Complexity

Time Complexity: O(N)
Space Complexity: O(N)

The Time Complexity of the algorithm is linear as we are just iterating through the string twice
The Space Complexity is also linear because in the worst case all the chars will be stored in the hashmap

Java Code

import java.util.HashMap;
import java.util.Map;
     
class StringOperations {

    public static Character getFirstNonRepeatingCharacter(String givenString) {
       
        // Iterate through the string and find count of each characters
       Map charCount = new HashMap();
       
       for (int index = 0; index < givenString.length(); index++) {
         Character currentChar = givenString.charAt(index);
         if (charCount.containsKey(currentChar)) {
           charCount.put(currentChar, charCount.get(currentChar) + 1);
         } else {
           charCount.put(currentChar, 1);
         }
       }
     
       // Iterate through the string and
       // return the first character having count equal to 1
       for (int i = 0; i < givenString.length(); i++) {
         Character currentChar = givenString.charAt(i);
         // Returning 1 when the count of character is 1
         if (charCount.get(currentChar) == 1) {
           return currentChar;
         }
       }
     
       // All Characters are repeating
       return '#';
    }
     
    public static void main(String[] args) {
       
       String string1 = "madam";
       System.out.println("The first non repeating character in " + string1 + " is: " + 
            getFirstNonRepeatingCharacter(string1));
     
       String string2 = "fundesk";
       System.out.println("The first non repeating character in " + string2 + " is: " + 
            getFirstNonRepeatingCharacter(string2));
     
       String string3 = "anna";
       System.out.println("The first non repeating character in anna is:  " + 
            getFirstNonRepeatingCharacter(string3));
    }
}

Output

The first non repeating character in madam is: d
The first non repeating character in fundesk is: f
The first non repeating character in anna is: #