Find first non repeated character in a String

Table of Contents [hide]

First approach:
- Algorithm:
- Program:
Second Approach:
- Algorithm:
- Program:

One of the interview question is “How will you find first non repeating character in String.”

For example:
If input string is “analogy”, then program should return ‘n’
If input string is “easiest”, then program should return ‘a’

First approach:

We will use [LinkedHashMap](https://java2blog.com/linkedhashmap-in-java-with-example/ “LinkedHashMap”) to find first non repeating character in String.

Algorithm:

Get character while looping over String
Put this character in LinkedHashMap with count. If character is already there, increase count by 1.
Get count from LinkedHashMap while iterating. If count is 1,return that character as LinkedHashMap maintains insertion order.

Program:

package org.arpit.java2blog.algo;

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

public class GetFirstNonRepeatingCharacterMain {
 public static void main(String[] args) {
  System.out
    .println("First non repeated character for String analogy is : "
      + getNonRepeatedCharacter("analogy"));
  System.out
    .println("First non repeated character for String easiest is : "
      + getNonRepeatedCharacter("easiest"));
 }

 public static Character getNonRepeatedCharacter(String str) {
  Map<Character, Integer> countCharacters = new LinkedHashMap<Character, Integer>();
  for (int i = 0; i < str.length() - 1; i++) {
   Character c = str.charAt(i);
   if (!countCharacters.containsKey(c)) {
    countCharacters.put(c, 1);
   } else {
    countCharacters.put(c, countCharacters.get(c) + 1);
   }
  }
  // As LinkedHashMap maintains insertion order, first character with
  // count 1 should return first non repeated character
  for (Entry<Character, Integer> e : countCharacters.entrySet()) {
   if (e.getValue() == 1)
    return e.getKey();

  }
  return null;

 }
}

package org.arpit.java2blog.algo;

import java.text.*;

import java.util.*;

import java.util.Map.Entry;

public class GetFirstNonRepeatingCharacterMain {

public static void main(String[] args) {

System.out

.println("First non repeated character for String analogy is : "

+ getNonRepeatedCharacter("analogy"));

System.out

.println("First non repeated character for String easiest is : "

+ getNonRepeatedCharacter("easiest"));

}

public static Character getNonRepeatedCharacter(String str) {

Map<Character, Integer> countCharacters = new LinkedHashMap<Character, Integer>();

for (int i = 0; i < str.length() - 1; i++) {

Character c = str.charAt(i);

if (!countCharacters.containsKey(c)) {

countCharacters.put(c, 1);

} else {

countCharacters.put(c, countCharacters.get(c) + 1);

}

// As LinkedHashMap maintains insertion order, first character with

// count 1 should return first non repeated character

for (Entry<Character, Integer> e : countCharacters.entrySet()) {

if (e.getValue() == 1)

return e.getKey();

}

return null;

}

When you run above program, you will get following output:

First non repeated character for String analogy is : n
First non repeated character for String easiest is : a

First non repeated character for String analogy is : n

First non repeated character for String easiest is : a

Second Approach:

Algorithm:

Iterate through each character of string.
If lastIndexOf and indexOf return same value, then it is first non repeating character in the String.

Program:

package org.arpit.java2blog.algo
public class GetFirstNonRepeatingCharacterMain
{
 public static void main(String[] args)
 {
        System.out.println("First non repeated character for String analogy is : "+getNonRepeatedCharacter("analogy"));
        System.out.println("First non repeated character for String easiest is : "+getNonRepeatedCharacter("easiest"));
 }
 public static Character getNonRepeatedCharacter(String str)
 {     char charaaray[]=str.toCharArray();
       for (int i=0; i<str.length();i++)
      {
          if (str.lastIndexOf(charaaray[i]) == str.indexOf(charaaray[i]))
               return charaaray[i];
      }
  return null;
 }
}

package org.arpit.java2blog.algo

public class GetFirstNonRepeatingCharacterMain

{

public static void main(String[] args)

{

System.out.println("First non repeated character for String analogy is : "+getNonRepeatedCharacter("analogy"));

System.out.println("First non repeated character for String easiest is : "+getNonRepeatedCharacter("easiest"));

}

public static Character getNonRepeatedCharacter(String str)

{ char charaaray[]=str.toCharArray();

for (int i=0; i<str.length();i++)

{

if (str.lastIndexOf(charaaray[i]) == str.indexOf(charaaray[i]))

return charaaray[i];

}

return null;

}

When you run above program, you will get following output:

First non repeated character for String analogy is : n
First non repeated character for String easiest is : a

First non repeated character for String analogy is : n

First non repeated character for String easiest is : a

Please go through Common java interview Programs for more such programs.

Was this post helpful?

Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.

Find first non repeated character in a String

First approach:

Algorithm:

Program:

Second Approach:

Algorithm:

Program:

Was this post helpful?

Author

Leave a Reply Cancel reply

Categories

Popular Posts

Let’s be Friends

First approach:

Algorithm:

Program:

Second Approach:

Algorithm:

Program:

Was this post helpful?

Related posts:

Share this

Author

Leave a Reply Cancel reply

Let’s be Friends