Wednesday, September 20, 2023

3 ways to Find First Non Repeated Character in a String - Java Programming Problem Example

Write a Java program to find the first non-repeated character in a String is a common question on coding tests. Since String is a popular topic in various programming interviews, It's better to prepare well with some well-known questions like reversing String using recursion, or checking if a String is a palindrome or not. This question is also in the same league. Before jumping into the solution, let's first understand this question. You need to write a function, which will accept a String and return first non-repeated character, for example in the world "hello", except 'l' all are non-repeated, but 'h' is the first non-repeated character.

Similarly, the word "swiss" 'w' is the first non-repeated character. One way to solve this problem is by creating a table to store the count of each character, and then picking the first entry which is not repeated. The key thing to remember is order, your code must return the first non-repeated letter.

By the way, In this article, we will see 3 examples to find the first non-repeated character from a String. 

Our first solution uses LinkedHashMap to store character count since LinkedHashMap maintains insertion order and we are inserting a character in the order they appear in String, once we scanned String, we just need to iterate through LinkedHashMap and choose the entry with value 1. 

Yes, this solution requires one LinkedHashMap and two for loops.




Our second solution is a trade-off between time and space, to find the first non-repeated character in one pass. This time, we have used one Set and one List to keep repeating and non-repeating characters separately. 

Once we finish scanning through String, which is O(n), we can get the magic character by accessing List which is an O(1) operator. Since List is an ordered collection get(0) returns the first element.

Our third solution is also similar, but this time we have used HashMap instead of LinkedHashMap and we loop through String again to find a first non-repeated character. In the next section, we will the code example and unit test for this programming question. 

You can also see my list of String interview Questions for more of such problems and questions from the Java programming language.


How to find First Non-Repeated Character from String? Example

How to find first non-repeated character in a String in JavaHere is the full code sample of finding first duplicate character in a given String. This program has three method to find first non-repeated character. Each uses their own algorithm to do this programming task. First algorithm is implemented in getFirstNonRepeatedChar(String str) method. 

It first gets a character array from given String and loop through it to build a hash table with characters as key and their count as value. 

In the next step, It loop through LinkedHashMap to find an entry with value 1, that's your first non-repeated character, because LinkedHashMap maintains insertion order, and we iterate through character array from beginning to end. 

The bad part is it requires two iterations, first one is proportional to number of character in String, and second is proportional to number of duplicate characters in String. In worst case, where String contains non-repeated character at end, it will take 2*N time to solve this problem.

Second way to find first non-repeated or unique character is coded on firstNonRepeatingChar(String word) ,this solution finds first non repeated character in a String in just one pass. It applies classical space-time trade-off technique. It uses two storage to cut down one iteration, standard space vs time trade-off.

Since we store repeated and non-repeated characters separately, at the end of the iteration, the first element from List is our first non-repeated character from String. This one is slightly better than the previous one, though it's your choice to return a null or empty string if there is no non-repeated character in the String.

The third way to solve this programming question is implemented in firstNonRepeatedCharacter(String word) method. It's very similar to first one except the fact that instead of LinkedHashMap, we have used HashMap. Since later doesn't guarantee any order, we have to rely on original String for finding first non-repeated character.

Here is the algorithm of this third solution. First step : Scan String and store count of each character in HashMap

Second Step : traverse String and get a count for each character from Map. Since we are going through String from first to last character, when count for any character is 1, we break, it's the first non repeated character. Here order is achieved by going through String again.


Java Program to find the first Unique Character in a given String

Here is our complete Java program to find the first non-repeated character from given String in Java:
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * Java Program to find first duplicate, non-repeated character in a String.
 * It demonstrate three simple example to do this programming problem.
 *
 * @author Javarevisited
 */
public class Programming {
    
    /*
     * Using LinkedHashMap to find first non repeated character of String
     * Algorithm :
     *            Step 1: get character array and loop through it to build a 
     *                    hash table with char and their count.
     *            Step 2: loop through LinkedHashMap to find an entry with 
     *                    value 1, that's your first non-repeated character,
     *                    as LinkedHashMap maintains insertion order.
     */
    public static char getFirstNonRepeatedChar(String str) {
        Map<Character,Integer> counts = new LinkedHashMap<>(str.length());
        
        for (char c : str.toCharArray()) {
            counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
        }
        
        for (Entry<Character,Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        throw new RuntimeException("didn't find any non repeated Character");
    }


    /*
     * Finds first non repeated character in a String in just one pass.
     * It uses two storage to cut down one iteration, standard space vs time
     * trade-off.Since we store repeated and non-repeated character separately,
     * at the end of iteration, first element from List is our first non
     * repeated character from String.
     */
    public static char firstNonRepeatingChar(String word) {
        Set<Character> repeating = new HashSet<>();
        List<Character> nonRepeating = new ArrayList<>();
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (repeating.contains(letter)) {
                continue;
            }
            if (nonRepeating.contains(letter)) {
                nonRepeating.remove((Character) letter);
                repeating.add(letter);
            } else {
                nonRepeating.add(letter);
            }
        }
        return nonRepeating.get(0);
    }


    /*
     * Using HashMap to find first non-repeated character from String in Java.
     * Algorithm :
     * Step 1 : Scan String and store count of each character in HashMap
     * Step 2 : traverse String and get count for each character from Map.
     *          Since we are going through String from first to last character,
     *          when count for any character is 1, we break, it's the first
     *          non repeated character. Here order is achieved by going
     *          through String again.
     */
    public static char firstNonRepeatedCharacter(String word) {
        HashMap<Character,Integer> scoreboard = new HashMap<>();
        // build table [char -> count]
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (scoreboard.containsKey(c)) {
                scoreboard.put(c, scoreboard.get(c) + 1);
            } else {
                scoreboard.put(c, 1);
            }
        }
        // since HashMap doesn't maintain order, going through string again
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (scoreboard.get(c) == 1) {
                return c;
            }
        }
        throw new RuntimeException("Undefined behaviour");
    }

}


JUnit Test to find First Unique Character

Here are some JUnit test cases to test each of this method. We test different kind of inputs, one which contains duplicates, and other which doesn't contains duplicates. Since program has not defined what to do in case of empty String, null String and what to return if only contains duplicates, you are feel free to do in a way which make sense.

import static org.junit.Assert.*;
import org.junit.Test;

public class ProgrammingTest {

    @Test
    public void testFirstNonRepeatedCharacter() {
        assertEquals('b', Programming.firstNonRepeatedCharacter("abcdefghija"));
        assertEquals('h', Programming.firstNonRepeatedCharacter("hello"));
        assertEquals('J', Programming.firstNonRepeatedCharacter("Java"));
        assertEquals('i', Programming.firstNonRepeatedCharacter("simplest"));
    }

    @Test
    public void testFirstNonRepeatingChar() {
        assertEquals('b', Programming.firstNonRepeatingChar("abcdefghija"));
        assertEquals('h', Programming.firstNonRepeatingChar("hello"));
        assertEquals('J', Programming.firstNonRepeatingChar("Java"));
        assertEquals('i', Programming.firstNonRepeatingChar("simplest"));
    }

    @Test
    public void testGetFirstNonRepeatedChar() {
        assertEquals('b', Programming.getFirstNonRepeatedChar("abcdefghija"));
        assertEquals('h', Programming.getFirstNonRepeatedChar("hello"));
        assertEquals('J', Programming.getFirstNonRepeatedChar("Java"));
        assertEquals('i', Programming.getFirstNonRepeatedChar("simplest"));
    }
}

If you can enhance these test cases to check more scenarios, just go for it. There is no better way to impress the interviewer than writing detailed, creative test cases, which many programmers can't think of or just don't put effort to come up.

That's all on How to find the first non-repeated character of a String in Java. We have seen three ways to solve this problem, although they use pretty much similar logic, they are different from each other. 

This program is also very good for beginners to master the Java Collection framework. It gives you an opportunity to explore different Map implementations and understand the difference between HashMap and LinkedHashMap to decide when to use them. 

By the way, if you know any other way to solve this problem, feel free to share. You can also share your interview experience, If you have faced this question in Interviews.

And now is the quiz time, What is the time complexity of this algorithm for finding first unique or non-repeated character in given String? can you improve this by using any data structure or different approach?

77 comments :

Rakesh Dewangan said...

If it's sorted then we can use XORing technique also.

Simerpreet Singh said...

Hi,

In Method getFirstNonRepeatedChar(str) , in first for loop of this method you have mentioned
counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);

count.get(c) should be Typecasted to int : (int) count.get(c)+1.

Thanks


SARAL SAXENA said...

@Javin.. perfect article lem me add one more logic which I have tried...

public static Character findFirstNonRepeated(String input) {
// create a new hashtable:
Hashtable hashChar = new Hashtable();

int j, strLength;
Character chr;
Object oneTime = new Object();
Object twoTimes = new Object();

strLength = input.length();

for (j = 0; j < strLength; j++) {
chr = new Character(input.charAt(j));
Object o = hashChar.get(chr);

/*
* if there is no entry for that particular character, then insert
* the oneTime flag:
*/
if (o == null) {
hashChar.put(chr, oneTime);
}
/*

*/
else if (o == oneTime) {
hashChar.put(chr, twoTimes);
}
}

/*
* go through hashtable and search for the first nonrepeated char:
*/

int length = strLength;
for (j = 0; j < length; j++) {
chr = new Character(input.charAt(j));
Object c = null;
if (hashChar.get(chr) == oneTime)
return chr;
}
/*
* this only returns null if the loop above doesn't find a nonrepeated
* character in the hashtable
*/
return null;

}

Anonymous said...

Second solution can use list only to save space.. also alternatively try hashset or int[256] . :junmin

Unknown said...

Hi all,

This problem can be solved with Regex.

public static char firstNonRepeatingCharWithRegex(String word) {
for (int i = 0; i < word.length(); i++) {
char letter = word.charAt(i);
if (!word.matches("(.*)" + letter + "(.*)" + letter + "(.*)")) {
return letter;
}
}
return ' ';
}

BlueOcean said...

this is my solution:
public static Character firstNonRepeatChar(String s){
int[] found = new int[256];
char[] chars = s.toCharArray();

for(int i=0; i< chars.length; i++)
found[chars[i]]++;

for(int i=0; i< chars.length; i++){
if(found[chars[i]]==1)
return chars[i];
}
return null;
}

Anonymous said...

Hi i got all the non repeated characters when i ran the first method..Please suggest..

Unknown said...

char charaaray[]=str.toCharArray();
for (int i=0; i<str.length();i++)
{
int lastindex=str.lastIndexOf(charaaray[i]);
if (lastindex == str.indexOf(charaaray[i]))
return charaaray[i];
}

ಮಾಂತೇಶ said...

import java.util.Scanner;
public class NonrptdChar
{
public static void main(String[] args)
{

Scanner s=new Scanner(System.in);
System.out.println("Enter the String ");
String str=s.next();
char[] arr=new char[str.length()];
for(int j=0;j<arr.length;j++)
{
arr[j]=str.charAt(j);
}
char found=searchchar(str,arr);
System.out.println("The first non repeated char is "+found);
}
public static char searchchar(String a,char[] b)
{
int i=0;
while(i!=a.length())
{
int count=0;
for(int j=0;j<b.length;j++)
{
if(i!=j)
{
if(a.charAt(i)!=b[j])
{
count++;
}
}
if(count==a.length()-1)
{
return a.charAt(i);
}
}
i++;
}
return 0;
}
}

Anonymous said...

assertEquals('e', Programming.firstNonRepeatingChar("hhhello"));

Edwin W.T. said...

for(int i=0;i<word.length();i++){
if(word.indexOf(word.charAt(i))==word.lastIndexOf(word.charAt(i))){
System.out.println(word.charAt(i));
break;
}
}

Anonymous said...

The programs you have mentioned does not work as programmed if the repeating characters are in different case (upper case and lower case).
For eg:- if I provide input as "Swiss" than the first non repeating character would be 'S'.
if I provide input as "swiss" than the first non repeating character would be 'w'.

Can you please help me out if is there any way so that upper case and lower case does't make any difference.

Unknown said...

public class StringDemo {

public char getNonRepeatedChar(String inputString)
{
char ch = ' ';
char [] charArray = inputString.toCharArray();
for(int i=0;i<inputString.length();i++)
{

if(inputString.indexOf(String.valueOf(charArray[i]),inputString.indexOf(String.valueOf(charArray[i]))+1)==-1)
{
ch = charArray[i];
break;
}
}
return ch;
}

public static void main(String[] args) {
System.out.println(new StringDemo().getNonRepeatedChar("amitami"));
}
}

Victor Rodriguez said...

public static char firstUniqueChar(String string) {
int[] counts = new int['~' - ' '];

for (int x = 0; x < string.length(); x++) {
++counts[string.charAt(x) - ' '];
}

for (int x = 0; x < string.length(); x++) {
char c = string.charAt(x);
if (counts[c - ' '] == 1) {
return c;
}
}

return 0;
}

Nishant said...

ANOTHER METHOD :-
Loop through the character array and try the firstIndex and lastIndex of the particular character, if both are same ,print the the character i.e. THE FIRST NON-REPEATED character

MUNAWAR P . . . said...

String str="RAMAR";
for(char ch:str.toCharArray()){
if(str.indexOf(ch)==str.lastIndexOf(ch)){
System.out.println("Non repeating: "+ch);
}
}

okay!!!! said...

import java.util.Scanner;
public class Find_it {
static void main(String []args){
Scanner scan =new Scanner(System.in);
System.out.println("enter string: ");
String s=scan.nextLine();
char c=detct(s);
System.out.println("first repeated word is: "+c);
scan.close();
}
public static char detct(String t)
{for(int i=0;i1)
{return p; }
}
return 0;
}}

javin paul said...

@Unknown, it seems blogger has eaten your solution due to < and > meta characters. detect method is not complete, please past html encoded code or just replace < or > with '<' and '>'

Jeffery said...

In the second solution, we should use linkedhashset instead of list.

javin paul said...

@Jeffery, Can you please explain why we should use LinkedHashSet instead of List?

Anonymous said...


//first non repeating character by using collection

public static void firstNonRepeatedChar(String str){
char[] cArr= str.toCharArray();
Set s1=new LinkedHashSet();
Set s2= new HashSet();
for(char c :cArr){
if(s1.add(c)){

}
else{
s2.add(c);
}
s1.removeAll(s2);
}
if(s1.size()>0){
Iterator itr=s1.iterator();
if(itr.hasNext()){
System.out.println("first non repeated character="+itr.next());
}
}
else{
System.out.println("no unique character");
}
}

Anonymous said...

Check out the Oracle docs for Java String class.

It has methods to support finding first and last index of a given char within a String.
Additionally chars within the String can be iterated like an array WITHOUT having to explicitly convert the String into char[ ].

Using these would greatly simplify the code.

https://docs.oracle.com/javase/7/docs/api/java/lang/String.html

Anonymous said...

Hi,

I have one doubt, in the method getFirstNonRepeatedChar(str) you created one hashmap and inserting chars and counts. my doubt is, the hashmap is built on hashing technique, how can you sure the order of chars in the map.

Unknown said...

it is very easy....you can do it without collection in java..

public class FirstNonRepeatedString{

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);
String input = sc.next();
char process[] = input.toCharArray();
boolean status = false;
int index = 0;
for (int i = 0; i < process.length; i++) {
for (int j = 0; j < process.length; j++) {

if (i == j) {
continue;
} else {
if (process[i] == process[j]) {
status = false;
break;
} else {
status = true;
index = i;
}
}

}
if (status) {
System.out.println("First non-repeated string is : " + process[index] + " INDEX " + index);
break;
}
}
}
}

srinidhi said...

in python 2.7
def first(str):
letters = list(str)
l = []
for i in letters:
if i not in l:
l.append(i)
else:
l.remove(i)
return l[0]

if __name__ == '__main__':
print first(raw_input())

javin paul said...

@srinidhi, no doubt python solution is short but its not as readable as Java. It's not about algorithm but the language itself :-). Being a statically typed language, Java is much more readable than Python.

GOPIKRISHNA said...

String s="gopikrishnagopikrishn";
int count=1;
for(int i=0;i<s.length();i++)
{
char ch=s.charAt(i);
if(s.indexOf(ch) == s.lastIndexOf(ch))
{
System.out.print(ch);
count=0;
break;
}
}
if(count==1)
System.out.print("All Characters Are repeated");

Unknown said...

Why did you use Set for repeating and List for non-repeating in the 2nd algorithm?

Unknown said...

private String getFirstNonRepeatingCharacter(String word) {
List mList = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
char letter = word.charAt(i);

if (mList.contains(letter)) {
mList.remove((Character) letter);
} else {
mList.add(letter);
}
}

if (mList.size() > 0)
return mList.get(0).toString();
else
return "No any non repeating character found";
}

Anonymous said...

final String name = "ABCDABCE";


char result = findnonrepeativecharacters(name);

Log.d("result", Character.toString(result));




private char findnonrepeativecharacters(String name) {

char non_repeatedive_char = 0;
char[] characters = name.toCharArray();
Arrays.sort(characters);
for (int i = 0; i < characters.length-1; i++) {

if (characters[i] != characters[i + 1]) {

non_repeatedive_char = characters[i];
}

}
return non_repeatedive_char;
}

Unknown said...

what is the difference between first and third method what difference does it make if we are using HashMap instead of LinkedHashMap, you followed same process , please clarify this

javin paul said...

Hello Mahendra, the difference comes from the behavior, LinkedHashMap keeps insertion order i.e it maintains the order on which duplicate characters are inserted on it, but HashMap doesn't do it. Hence to find the first duplicate character, you can see in first example we iterate over Map but in second example we iterate over String.

Unknown said...

Check out this simple code:

import java.util.*;

public class NonRepeatChar {

public static void main(String[] args) {

String str = "awswasrstuv";
Character c;

boolean [] visited = new boolean[str.length()];

List list = new ArrayList();

for(int i = 0; i < str.length(); i++){
if(!list.contains(str.charAt(i))) {
visited[i] = true;
list.add(str.charAt(i));
}
else{
c = str.charAt(i);
visited[list.indexOf(c)] = false;
//System.out.println("char " + c);
}

}

//System.out.println("Print List " + list);

for(int i=0; i < str.length(); i++){
if(visited[i]){
System.out.println("First non repeating character " + str.charAt(i));
break;
}
}

}

}

Unknown said...

Consider that you have an ordered array aabbcddde
Then the only thing you have to do is just go through the index check if both of your neigbours are different. :)

Unknown said...

Hi ,

Why have you used Nonrepeating.remove((Character)letter) in the seconde method.
why can't we use Nonrepeating.remove(c);

pakalu papito said...

in the second method we dont need the Set. Can be done by ArrayList alone.

javin paul said...

@Unknown, we need to used remove(Character) in the second method because by default c is represented as int value which means remove(c) will translate to remove(int) which can remove object from index e.g. remove('A') can remove object at 65th index (ASCII value of 'A") instead of removing object 'A' from the list. This problem happens because of overloading and autoboxing, you can read more about it here

javin paul said...

@pakalu, can you explain more?

Unknown said...


import java.util.Scanner;
public class JavaApplication21 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("Program to print first non repeated characters in a string");
System.out.println("Enter the string");
String s1=sc.next();
char c1=' ';
int flag=0;
for(int i=0;i<s1.length();i++){
int count=0;
for(int j=0;j<s1.length();j++){
if(j<i && s1.charAt(i)==s1.charAt(j)){
break;
}
if(s1.charAt(i)==s1.charAt(j)){
count++;
}
if(j==s1.length()-1 && count==1){
c1=s1.charAt(i);
flag=1;
}
}
if(flag==1){
break;
}
}
if(flag==1){
System.out.println("The first non repeated characters in the string " +s1+ " is: " +c1);
}
}
}

Unknown said...

import java.util.Scanner;
class Jmp
{
static int c=0;
public static void main(String args[])
{
System.out.println("Enter the String");
String str=new Scanner(System.in).nextLine();
for(int i=0;i<str.length();i++)
{
c=0;

for(int j=0;j<str.length();j++)
{
if(str.charAt(i)==str.charAt(j))
{
c++;
}

}
if(c==1)
{
System.out.println(str.charAt(i));
i=str.length();
break;
}
}
}
}

Unknown said...

In Java,

public static void main(String[] args) {
// TODO Auto-generated method stub
String str = "examinamtionex"; int count;
String[] strArr = str.split("");
ArrayList arrList=new ArrayList();
for (int i = 0; i < strArr.length; i++) {
count=0;
if(!arrList.contains(strArr[i]))
{
arrList.add(strArr[i]);
for (int j = i+1; j < strArr.length; j++) {
if(strArr[i].equals(strArr[j]))
{
count++;
}
}
if(count==0)
{
System.out.println("First Non Repeated Character is: " + strArr[i] + " --- at index ---" + i);
break;
}
}
}
}

java said...

First Non Repeated Character..

class Test
{
static void firstNotRepeatedChar(String s)
{
char[] arr=s.toCharArray();


for(int i=0; i<arr.length; i++)
{
int count=0;
for(int j=0; j<arr.length; j++)
{

if(arr[i]==arr[j])
count++;
}

if(count==1)
{
System.out.println("First Not Repeated Character is :"+arr[i]);
break;
}
}
}


public static void main(String... args)
{
firstNotRepeatedChar("javatutorial");
}
}

satish said...

package com.remove.lastchar;

public class FirstNonRepetChar {

public static void main(String[] args) {

String s = "shatiatish";
char [] ch = s.toCharArray();
for(char c : ch) {
if(s.lastIndexOf(c)==s.indexOf(c)) {
System.out.println("First non repeat char : " + c);break;
}
}
}
}

what about this it's easy ....

Pawan said...

package StringRelated;

public class First_Non_Repeat {

public static void main(String[] args) {
String s="PawanP";
int count=0;
char c='\0';
for(int i=0;i<s.length();i++)
{
count=0;
for(int j=0;j<s.length();j++)
{
if(s.charAt(i)==s.charAt(j))
{
count++;

}
}

if(count==1) {
c=s.charAt(i);
break;

}
}
System.out.println("First Non_Repeat Character is "+c);
}

}

Rajasekhar said...

I think this one is better


package com.array.example;

public class FirstNonRepeat {

public static void main(String[] args) {
String s = "swiss";
pairSum(s);

}

private static void pairSum(String sd) {
char[] c = sd.toCharArray();
char[] c1;
boolean status = false;
int index = 0;
for (int i = 0; i < c.length; i++) {
for (int j = i + 1; j < c.length; j++) {
if (c[i] == c[j]) {
status = false;
break;
} else {
status = true;
index = i;
}
}
if (status == true) {
System.out.println(status + " " + index + " " + c[index]);
break;
}
}

}
}

Anonymous said...

List.contains runs in O(n) time so for the second example it's worst-case O(n^2)

Unknown said...

private static void firstNonRepeat(String str)
{
int[] array = new int[256];
for (int i = 0; i <= str.length() - 1; i++) {
++array[str.charAt(i)];
}

for (int i = 0; i <= str.length() - 1; i++) {
if (array[str.charAt(i)] == 1) {
System.out.println("First Non Repeated Char is " + str.charAt(i));
break;
}
}
}

arjun said...

import java.util.*;

public class FirstNonRepeatChar{

public static void main(String[] args) {
Scanner scanner= new Scanner(System.in);
String line=scanner.nextLine();


for(char c: line.toCharArray())
{

if((line.lastIndexOf(Character.toString(c))==line.indexOf(Character.toString(c))))
{
System.out.println(c);
break;
}
}



}
}

Unknown said...

public class Firstnonrepeated {
public static void main(String[] args) {
String s = "abcdefghija";
String s1 = s.toLowerCase();
int count = 0;
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j < s1.length(); j++) {
if (s1.charAt(i) == s1.charAt(j)) {
count++;
}
}
if(count!=i+1){
System.out.println("The first non repeated character is: "+s.charAt(count));
break;
}
}
}
}

Unknown said...

I didn't go through all the comments, so I don't know if the the following solution has already been discussed. Anyway, the 3 approaches are good but I found a better one I think.
In the second solution, List.contains() and List.remove() are not constant but O(n) so second solution is O(n x n).
In the third solution you're still traversing the string one more time (even if not the whole string).

If you use an array of frequency and LinkedHashSet, you will only remove from the set characters that appear more than once, whilst keeping updating the frequency array. LinkedHashSet keeps order of insertion and has O(1) add and O(1) remove. You don't need contains() to check.

Following the solution I tested supposing you only have lower case characters (otherwise initialise the int array as with 256):

public static char firstNonRepeatableLetter(String s) {
final int freq[] = new int[26];
final HashSet hashSet = new LinkedHashSet<>();
for (char c : s.toCharArray()) {
freq[c - 'a']++;

hashSet.add(c);

if (freq[c - 'a'] > 1)
hashSet.remove(c);
}
return hashSet.isEmpty() ? '0' : hashSet.iterator().next(); // or throw exception if empty
}

Unknown said...

If you just want first non-repeating character, there is no need of set

Jorge Flores said...

This is another implementation:

public static Character getFirstUniqueCharacter(final String phrase) {

final char[] charList = phrase.toCharArray();

for (final char item: charList) {
final String updatedPhrase = phrase.replaceAll(String.valueOf(item), "");
if (phrase.length() == updatedPhrase.length() + 1) {
return item;
}
}

return null;
}

This isn't the fastest but at least it's short.

Anonymous said...

//char
char[] chars={'a','b','c','d','d','c','e'};
int lowest1=chars.length;
HashMap myMap1=new HashMap();
for(int i=0;i<chars.length;i++)
{
if(myMap1.containsKey(chars[i]))
myMap1.remove(chars[i]);
else
myMap1.put(chars[i], i);
}
for(Character m:myMap1.keySet())
{
if(myMap1.get(m)<lowest1)
lowest1=myMap1.get(m);
}
System.out.print("lowest:"+chars[lowest1]);

Unknown said...

How about it solving by finding the index of character in the rest of the string? If it's found that means the character is repeated and move ahead. Else that indicates it's a unique letter. Stop iteration and return.

char[] chars = input.toCharArray();
boolean found = false;
for (int i = 0; i < chars.length; i++) {
String restOfString = input.substring(0, i) + input.substring(i + 1);
if (restOfString.indexOf(chars[i]) < 0) {
System.out.println("First non-repeated character in " + input + " is: " + chars[i] + " at index: " + i);
found = true;
break;
}
}

if (!found) {
System.out.println("Non-repeated character not found");
}

Anonymous said...

package aaa_demo;

import java.util.ArrayList;
import java.util.List;

public class FirstNonRepeating {

public static void main(String[] args) {
String str = "hihelloiamshashi";
System.out.println("This The Given String:" + str);
List repeating = new ArrayList<>();
for (int i = 0; i < str.length(); i++) {

if (repeating.contains(str.charAt(i))) {
repeating.remove((Character) str.charAt(i));

} else {
repeating.add(str.charAt(i));
}

}
System.out.println(repeating.get(0));
}
} this worked for me

sanjay boga said...

#include
void main()
{
char a[] = "sanjay";
//char b[] = "sanjay";
int i,j;
int n = strlen(a);

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if((a[i]==a[j])&&(i!=j))
break;


}
if(j==n)
{
printf("%c",a[i]);
break;
}
}
}

o/p:
s

Unknown said...

Hey javin, between the two approaches where you use maps, why did you use for each in the first and a simple for loop in the second one?

srinu said...

package com.pageTest;

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

public class DuplicateCharacters {

private Character testFirstNonRepeatedCharacter(String string) {

int counter = 0;
Map characters = new LinkedHashMap<>();
char chars[] = string.toUpperCase().toCharArray();
for (int i = 0; i < chars.length; i++) {

for (int j = 0; j < chars.length; j++) {
if (chars[i] == chars[j]) {
counter++;

}
}
characters.put(chars[i], counter);
counter = 0;
}
return characters.keySet().stream().filter(x->characters.get(x)==1).collect(Collectors.toList()).get(0);
}

public static void main(String[] args) {
DuplicateCharacters duplicateCharacters = new DuplicateCharacters();
System.out.println(duplicateCharacters.testFirstNonRepeatedCharacter("simplest"));

}

}

Unknown said...

I want the program to return true when the characters are repeating in the given string and return false when characters are not repeating in the given string in java

Unknown said...

class AngularMinds7{
public static void main(String[] args) {
String s="hellowhhdhdlo";
char[] ch=s.toCharArray();
for(int i=0;i<ch.length;i++){
int count=0;
for(int j=i+1;j<ch.length;j++){
if(ch[i]==ch[j]){
ch[j]=' ';
count++;
break;
}
}
if(count==0){
System.out.println(ch[i]);
break;
}
}
}
}

Alex said...

list.contains(n) is not O(1) is O(2),
lists in java are not based on hashcode

javin paul said...

what do you mean by O(2), O(1) is same as O(2) I mean constant time. List doesn' use hashcode but they use array which provides O(1) access if you know index. In fact hash table is based upon array.

Anonymous said...

Hi, i write code this --------->

public class Test {
public static String getString() {
Scanner scanner = new Scanner(System.in);
System.out.print("cumle----->");
String sentence = scanner.nextLine();
return sentence;
}

public static void getF(String sentence) {
char let = ' ';
int count = 0;
for (int i = 1; i < sentence.length(); i++) {
String sub = sentence.substring(i);
for (int j = 0; j < sentence.length(); j++) {
let = sentence.charAt(j);
if (sub.contains(String.valueOf(let))) {
continue;
} else {System.out.println("resul " + let);
return;}
}
}
}
public static void main(String[] args) {
NonRpeat.getF(NonRpeat.getString());
main(args);
}

Anonymous said...

public class Test {
public static String getString() {
Scanner scanner = new Scanner(System.in);
System.out.print("cumle----->");
String sentence = scanner.nextLine();
return sentence;
}

public static void getF(String sentence) {
char let = ' ';
int count = 0;
for (int i = 1; i < sentence.length(); i++) {
String sub = sentence.substring(i);
for (int j = 0; j < sentence.length(); j++) {
let = sentence.charAt(j);
if (sub.contains(String.valueOf(let))) {
continue;
} else {System.out.println("resul " + let);
return;}
}
}
}
public static void main(String[] args) {
NonRpeat.getF(NonRpeat.getString());
main(args);
}

Unknown said...

public class FirstNonCurrenceChar {

public static void main(String[] args) {
String str="ICECREAMOVERICECREAMO";
char[] c= str.toCharArray();

for(int i=0;i<c.length;i++)
{
boolean unique=true;
for(int j=0;j<c.length;j++)
{
if(c[i]==c[j] &&( i!=j))
{
unique=false;
break;
}

}
if(unique)

System.out.println(c[i]);
}

}

}

Unknown said...

Another Solution
===================
public class FirstnonrepeatedcharacterofString {

public static void main(String[] args) {
String str= "avaveccdhht";
char[] chars =str.toCharArray();

for(char c : chars) {
int findex = str.indexOf(c);
int lastIndex = str.lastIndexOf(c);
if(findex ==lastIndex ) {
System.out.println(c);
break;

}
}

}

}

javin paul said...

Good, keep it up

chetan said...

static Character findFirstNonRepeatableChar(String s) {

Map map = new LinkedHashMap();
for (Character ch : s.toCharArray()) {
map.put(ch, map.containsKey(ch) ? map.get(ch) + 1 : 1);
}
return map.entrySet().stream().filter(x -> x.getValue() == 1).findFirst().get().getKey();
}

Dilip Meghwal said...

public class Test{
public static void main(String[] args) {
int[] arr = {1,1,5,3,1,1,2,2};
findDuplicates(arr);
}

@SuppressWarnings("null")
public static void findDuplicates(int[] arr) {
ArrayList lst = new ArrayList();
for(int i=0; i<arr.length; i++) {
lst.add(arr[i]);
}
System.out.println(lst.stream().distinct().collect(Collectors.toList()));
}
}

Milesh Kotadia said...

import java.util.*;
public class FirstNonRepeatative{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
char[] arr=str.toCharArray();
ArrayList al=new ArrayList();
HashMap hm=new HashMap();
for(Character ch:arr) {
if(hm.containsKey(ch)) {
hm.put(ch, hm.get(ch)+1);
al.remove(ch);

}
else {
hm.put(ch, 1);
al.add(ch);
}
}
System.out.println(al.get(0));
}
}

Anshul Katta said...

in Java 8

LinkedHashMap charCount = new LinkedHashMap();
String word = "simplest";
Stream charStream = word.chars().mapToObj(i -> (char) i);

charStream.forEach(c ->
charCount.put(c, (charCount.get(c) == null) ? 1 : charCount.get(c) + 1));

Optional> result = charCount.entrySet().
stream().
filter(c -> c.getValue() == 1).
findFirst();

System.out.println(result);

javin paul said...

Yes, findFirst() can do the job for you. Also stream is lazy so better performance.

Anonymous said...

This is programm done by me in very simple steps in java
import java.util.*;
import java.io.*;
// First non repeated char
public class NonReapChar
{
public static void main(String arg[])
{

Scanner sc=new Scanner(System.in);
System.out.println("Enter string1"); // Enter a input
String s1=sc.nextLine();
int Slen=s1.length(); // length of string

int count=0;

char[] c1=s1.toCharArray(); // string to array beacuse string is immuatable object

for(int i=0;i<Slen;i++)
{
count=0;

for(int j=i+1;j<Slen;j++)
{
if(c1[i]==c1[j])
{
count++;
break;
}
}
if(count==0)
{
System.out.println(c1[i]);
break;
}

}

}
}

javin paul said...

Hello @Anonymous, have you tested your solution?

PradeepSen said...

private String getFirstNonRepeatedChar(String input) {
String out = "";
if (input == null || input.isEmpty()) {
return out;
}

char[] chArray = input.toCharArray();

for (char ch : chArray) {
if (!out.contains(String.valueOf(ch))) {
out += ch;
} else {
out = out.replace(String.valueOf(ch), "");
}
}
return out.isEmpty() ? "" : String.valueOf(out.charAt(0));
}

Unknown said...

Just write
public static void main(String[] args) {
String str = "Java";
for(int i=str.length()-1;i>=0;i--) {
if(-1==str.substring(i+1, str.length()).indexOf(str.charAt(i)) && -1==str.substring(0,i).indexOf(str.charAt(i))) {
System.out.println(str.charAt(i));
break;
}
}
}

Anonymous said...

Its great coding

Post a Comment