Find the first non repeated character in a string [4 ways]

In written exams or in the technical interview of Amazon, you can easily find this question. So in order to help you with the preparation of interview, we are answering this question in this post.

First, we need to understand the question, we need to write an algorithm for  the first non repeated character in a string, for example:

Read Also :   Count number of words in the String

If the word "stress" is input then it should print  't'   as output.

If the word "teeter" is input then it should print  'r'   as output.

Method 1: Using indexOf() and lastIndexOf() [Easiest]

Using the indexOf() and lastIndexOf() method, we can find the first non-repeating character in a string in Java. The method indexOf() returns the position of the first occurrence of a given character in a string whereas method lastIndexOf() returns the position of the last occurrence of a given character in a string.

Logic

If positions returned by the indexOf() and lastIndexOf() methods of the specified character are the same, then that character is the first non-repeated character in a string.

public class FirstNonRepeatedCharFirst {
    public static void main(String args[]) {
     
        String inputStr ="teeter";

        for(char i :inputStr.toCharArray()){
        if ( inputStr.indexOf(i) == inputStr.lastIndexOf(i)) {
            System.out.println("First non-repeating character is: "+i);
            break;
        }
        }
    }
}

Output:
First non-repeating character is: r


Method 2: Using LinkedHashMap


Now, we should understand the pseudo algorithm or logic to achieve this task, code is given at the end of this post.

Logic

As we know a non-repeated character occurs only once in the string, so if we store the number of times
each alphabet appears in the string, it would help us identify which characters are non-repeated characters in the string. So we need to scan the whole string and determine the final counts of each character. Now scan the final values of each character in the string, the first character in the string with final count 1 is the first non-repeated character in the string.

Pseudo Algorithm

1.   First create the character count hash table.
 
          For each character
            If there is no value stored in the character
                     set it to 1.
            else
                     increment the value of the character by 1.

2.  Scan the string
           For each character
           return character if the count in hash table is 1.
           If no character have count 1, return null

Read Also :   Count total number of times each alphabet appears in the String


Code :



import java.util.*;
import java.util.Map.Entry;


public class FirstNonRepeatedCharSecond {
    
    public static void main(String[] args)
    {
        
        System.out.println(" Please enter the input string :" );
        Scanner in = new Scanner (System.in);
        String s = in.nextLine();
        char ch = firstNonRepeatedCharacter(s);
        System.out.println("The first non repeated character is :  " + ch);
    }
    
    public static Character firstNonRepeatedCharacter(String str)
    {
        HashMap<Character,Integer>  characterhashtable = 
                         new LinkedHashMap<Character ,Integer>();
        int length ;
        Character ch;
        length= str.length();  // Scan string and build hash table
        for (int i=0;i < length;i++)
        {
            ch = str.charAt(i);
            if(characterhashtable.containsKey(ch))
            {
                // increment count corresponding to ch
                characterhashtable.put(  ch ,  characterhashtable.get(ch) +1 );
            }
            else
            {
                characterhashtable.put( ch , 1 ) ;
            }
        }
        for(Entry<Character,Integer> entry: characterhashtable.entrySet())
        {
            if(entry.getValue() == 1)
                return entry.getKey();
        }
        return null;
    }
}    


Output:

first non repeated character in the string java example












Method 3: Using Set and ArrayList

Store the repeating and nonRepeating characters separately. At the end of the iteration, the first element of the nonRepeatingChars list is the first non-repeated character.

import java.util.*;

public class FirstNonRepeatedCharThird {
    
    
    public static Character firstNonRepeatedCharacter(String str)
    {
        Set<Character> repeatingChars = new HashSet<>();
        List<Character> nonRepeatingChars = new ArrayList<>();
        for(int i=0; i < str.length(); i++) {
            char letter = str.charAt(i);
            if(repeatingChars.contains(letter))
                continue;
            if(nonRepeatingChars.contains(letter)) {
                nonRepeatingChars.remove((Character) letter);
                repeatingChars.add(letter);
            }
            else {
                nonRepeatingChars.add(letter);
            }
        } 
        return nonRepeatingChars.get(0);
    }

    public static void main(String[] args)
    {
        
        System.out.println(" Please enter the input string :" );
        Scanner in = new Scanner (System.in);
        String s = in.nextLine();
        char ch = firstNonRepeatedCharacter(s);
        System.out.println("The first non repeated character is :  " + ch);
    }
}    

Output:
Please enter the input string : stress
The first non-repeated character is : t


Method 4: Using Java 8

import java.util.*;
import java.util.stream.*;

public class FirstNonRepeatedCharFour {
    
    public static Character findFirstNonRepeatableChar(String str) {
        Map<Character,Integer> map = new LinkedHashMap();
        for (Character ch : str.toCharArray()) {
            map.put(ch, map.containsKey(ch) ? map.get(ch) + 1 : 1);
        }
        return map.entrySet().stream().filter(x -> x.getValue() == 1).findFirst().get().getKey();
} 
    

    public static void main(String[] args)
    {
        String s = "hello";
        char ch = findFirstNonRepeatableChar(s);
        System.out.println( ch);
    }
}    

Output:
h

That's all for today, please mention in the comments in case you know any other way of finding the first non-repeated character in a string.

About The Author

Subham Mittal has worked in Oracle for 3 years.
Enjoyed this post? Never miss out on future posts by subscribing JavaHungry