Java Program to Find First Non-Repeated Character in a Given String

A very popular interview question for String is to write a Java program to find first non-repeated character in a given String. For example if given string is “always” then first non-repeated character is ‘l’ as character ‘a’ is repeated. Same way if String is “net” then first non-repeated character is ‘n’.

There are many ways to solve this problem, in this post I am giving 4 solutions to find first non-repeated character in a given String using Java.

If you are asked not to use any inbuilt API or data structure.
Solution using LinkedHashMap.
Solution using indexof() method of the String class.
Java 8 onward you can also use Stream API

Find first non-repeated character in a given String - Java program

Solution without using any data structure or API- If you are specifically asked not to use any Java collection or any library to find first non-repeated character in a given String then you can solve it using outer and inner for loops where outer loop iterates through the string one character at a time and in inner loop you will have to compare each character of the string with the character assigned in the outer loop. In case you find a match that character is not the non-repeated one. Make sure to skip the index of the character which you are comparing otherwise you will always find the match.

public class FirstOccurence {

 public static void main(String[] args) {
  String str = "zanzibar";
  
  boolean found = false;
  for(int i = 0; i < str.length(); i++){
   found = true;
   char c = str.charAt(i);
   //System.out.println("char " + c);
   for(int j = 0; j < str.length(); j++){
    //System.out.println("n-char " + str.charAt(j));
    // if found then set the boolean field as false
    // Also skip the char which is compared 
    if(c == str.charAt(j) && j != i){
     found = false;
     break;
    }
   }
   if(found){
    System.out.println("Character is "  + c);
    break;
   }
  }
  if(!found){
   System.out.println("No single character found");
  }
  
 }
}

Output

Character is n

Solution using LinkedHashMap- You can use LinkedHashMap to find the first non-repeated character in a String. Here LinkedHashMap is preferred over HashMap as LinkedhashMap maintains insertion order which helps to determine the first non-repeated character.

Logic here is to iterate over each character of the String and store it in a Map where character is the key and it's count is the value. Once you have all the characters in the Map, loop through the Map and find the first key where value is 1, that key will be the first non-repeated character in the String.

public class FirstOccurence {

 public static void main(String[] args) {
  String str = "always";
  Character ch = findWithLinkedHashMap(str);
  if(ch != null){
   System.out.println("Character is "  + ch);
  }else{
   System.out.println("No non-repeating character found");
  }
 }

 /**
  * Method to find non-repeated character using LinkedHashMap
  * @param str
  * @return
  */
 private static Character findWithLinkedHashMap(String str){
  Map<Character, Integer> charMap = new LinkedHashMap<Character, Integer>();
  for(int i = 0; i < str.length(); i++){
   Character c = str.charAt(i);
   // If found in map increment the count
   if(charMap.containsKey(c)){
    charMap.put(c, charMap.get(c) + 1);
   }else{
    charMap.put(c, 1); // First time insertion
   }
  }
  // Find the first character with count 1
  for(Entry<Character, Integer> entry : charMap.entrySet()){
   if(entry.getValue() == 1){
    return entry.getKey();
   }
  }
  return null;
 }
}

Output

Character is l

Solution using indexOf() method of the String class- Here logic used is; indexOf() method returns the index of the first occurrence of the specified character where as lastIndexOf() method returns the index of the last occurrence of the specified character. If both indexes are equal that means the searched character is there in the string only once.

public class FirstOccurence {

 public static void main(String[] args) {
  String str = "net";
  
  Character ct = findWithIndexComparison(str);
  
  if(ct != null){
   System.out.println("Character is "  + ct);
  }else{
   System.out.println("No non-repeating character found");
  }  
 }

 /**
  * 
  * @param str
  * @return
  */
 private static Character findWithIndexComparison(String str){
  for(int i = 0; i < str.length(); i++){
   Character c = str.charAt(i);
   if(str.indexOf(c) == str.lastIndexOf(c)){
    return c;
   }
  }
  return null;
 }
}

Output

Character is n

Using Stream API to find first non-repeated character - Logic here is similar to using LinkedHashMap directly (Solution 2). Here you will use Collectors.groupingBy() method and group the characters of the String along with their count which is stored in a LinkedHashMap.
From the Map you get the elements whose count is 1 using filter operation. Note that you get stream on Set view of the Map which returns element of type Map.Entry(). From the stream, you get after filtering, you get the first element using findFirst() which is the first non-repeated character in the String.

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class FindNonRepeated {
  public static void main(String[] args) {
    String str = "anyway";
    try {
      Character ch = findUsingStream(str);
      System.out.println("First non-repeated character- " + ch);
    } catch(RuntimeException e) {
      System.out.println(e.getMessage());
    }
  }
  
  private static Character findUsingStream(String str){
    Map<Integer, Long> characters = str.chars()
                                       .boxed()
                                       .collect(Collectors.groupingBy(Function.identity(), 
                                          LinkedHashMap::new, 
                                          Collectors.counting()));
     return (char)characters.entrySet()
                            .stream()
                            .filter(entry -> entry.getValue() == 1)
                            .findFirst()
                            .map(entry -> entry.getKey())
                            .orElseThrow(()->new RuntimeException("No non-repeating character found"))
                            .intValue();
  }
}

Output

First non-repeated character- n

That's all for this topic Java Program to Find First Non-Repeated Character in a Given String. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Wednesday, February 17, 2021

Java Program to Find First Non-Repeated Character in a Given String

Find first non-repeated character in a given String - Java program

No comments:

Post a Comment