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 a  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.

Here is also a nice memory map which highlights the time and space complexity of all solutions for finding first non-repeated or unique character in given String:

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

Here 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.

Other Useful Resources for Coding Interviews

• 10 Algorithms Books Every Programmer should Read
• 10 Free Courses to Learn Data Structure and Algorithms in Depth
• 20+ binary tree-based problems for interviews
• 10 Courses to Prepare for Programming Job Interviews
• How to design Vending Machine in Java
• 100+ Coding Interview Questions for Programmers
• 21 String Programming Interview Questions
• 5 Free Courses to Learn Algorithms for Interviews
• 10 Books to Prepare Technical Programming/Coding Job Interviews
• 100+ System Design Interview Questions 
• 75 Programming Interview Questions for Developers

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?