Find Non-Repeating Characters In a String In Java

Last Updated on July 4, 2023 by Prepbytes

You’ve been given a string S made up of lowercase Latin letters; find the first non-repeating character in S. In this article, we will delve deeper into the various techniques available to solve this problem.

Example of Non repeating characters in a string in Java:

Input:

“Prepbytes”

Output:

r

Explanation: "r” is the first character in the string that does not repeat.

We will look at six approaches to this problem in Java:

1. Using brute force
2. Utilizing the indexOf() function
3. Using a Hashmap to perform two traversals
4. Hashmap and single traversals
5. Making Use of a Frequency Array
6. Making use of sorting

Brute force approach to find non repeating characters in a string in Java

Following are steps to follow:

1. The idea is to loop through the string for each character.
2. Examine the string for the presence of the same character.
3. Return that character if the count of its occurrences is one.
4. Otherwise, look for the remaining characters.

Java Code

import java.io.*;
class Main {
    public static void main(String[] args) {
        String string = "prepbytes";
        int index = -1;
        char fnc = ' ';
        for (char i : string.toCharArray()) {
            if (string.indexOf(i) == string.lastIndexOf(i)) {
                fnc = i;
                break;
            }
            else {
                index += 1;
            }
        }
        if (index == 1) {
            System.out.println("Either all characters are repeating or "
                            + "string is empty");
        }
        else {
            System.out.println("First non-repeating character is " + fnc);
        }
    }
}

Output

First non-repeating character is r 

Time complexity : O(N^2)
Space complexity: O(1)

Using indexOf() function to find non repeating characters in a string in Java

Following are steps to follow:

1. The idea is to look for the current character in the string just after its first appearance.
2. If the character is found in the remaining string, it is returned.

Java Code

import java.util.*;

class Main {
public static void FirstNonRepeat(String s)
{

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

    if (s.indexOf(s.charAt(i), s.indexOf(s.charAt(i)) + 1) == -1) {
        System.out.println("First non-repeating character is "+ s.charAt(i));
        break;
    }
    }
    return;
}
public static void main (String[] args) {
    String s = "prepbytes";
    FirstNonRepeat(s);
}
}

Output

First non-repeating character is r 

Time complexity : O(N^2)
Space complexity: O(1)

Using Hashmap with two traversals to find non repeating characters in a string in Java

Following are steps to follow:

1. The goal is to calculate the frequency of each character in the string and determine which character has a unit frequency.
2. This task could be completed quickly by using a hash_map to map the characters to their respective frequencies.
3. And in which we can update the frequency of any character we come across in real time.

Java Code :

import java.io.*;
class Main {
    static final int NO_OF_CHARS = 256;
    static char count[] = new char[NO_OF_CHARS];
    static void getCharCountArray(String str)
    {
        for (int i = 0; i < str.length(); i++)
            count[str.charAt(i)]++;
    }
    static int firstNonRepeating(String str)
    {
        getCharCountArray(str);
        int index = -1, i;

        for (i = 0; i < str.length(); i++) {
            if (count[str.charAt(i)] == 1) {
                index = i;
                break;
            }
        }

        return index;
    }
    public static void main(String[] args)
    {
        String str = "prepbytes";
        int index = firstNonRepeating(str);

        System.out.println(
            index == -1
                ? "Either all characters are repeating or string "
                    + "is empty"
                : "First non-repeating character is "
                    + str.charAt(index));
    }
}

Output

First non-repeating character is r 

Time complexity : O(N)
Space complexity: O(256)

Using Hashmap with single traversal to find non repeating characters in a string in Java

Following are steps to follow:

1. The idea is to use a count array instead of a hash_map with a maximum of 256 characters.
2. Increase the count array’s capacity by storing not only counts but also the index of the first time a character appears.
3. So, instead of scanning the string, scan the count array to find the first non-repeater.

Java Code

import java.util.*;

class CountIndex {
    int count, index;
    public CountIndex(int index)
    {
        this.count = 1;
        this.index = index;
    }
    public void incCount() { this.count++; }
}
class Main {
    static final int NO_OF_CHARS = 256;

    static HashMap<Character, CountIndex> hm
        = new HashMap<Character, CountIndex>(NO_OF_CHARS);

    static void getCharCountArray(String str)
    {
        for (int i = 0; i < str.length(); i++) {
            if (hm.containsKey(str.charAt(i))) {
                hm.get(str.charAt(i)).incCount();
            }
            else {
                hm.put(str.charAt(i), new CountIndex(i));
            }
        }
    }
    static int firstNonRepeating(String str)
    {
        getCharCountArray(str);
        int result = Integer.MAX_VALUE, i;
        for (Map.Entry<Character, CountIndex> entry :
            hm.entrySet()) {
            int c = entry.getValue().count;
            int ind = entry.getValue().index;
            if (c == 1 && ind < result) {
                result = ind;
            }
        }

        return result;
    }
    public static void main(String[] args)
    {
        String str = "prepbytes";
        int index = firstNonRepeating(str);

        System.out.println(
            index == Integer.MAX_VALUE
                ? "Either all characters are repeating "
                    + " or string is empty"
                : "First non-repeating character is "
                    + str.charAt(index));
    }
}

Output

First non-repeating character is r 

Time complexity : O(N)
Space complexity: O(256)

Using Sorting to find non repeating characters in a string in Java

Following are steps to follow:

1. Make a count array with a maximum number of characters (256) and set all of its elements to -1.
2. Then loop through the string character by character, checking whether or not the array element with this character as the index is -1.
3. If it is -1, substitute i and. If it’s not -1, it means this character has already appeared, so change it to -2.
4. Finally, all repeating characters will be assigned a value of -2, while all non-repeating characters will be assigned the index where they appear.
5. To find the minimum or first index, simply loop through all of the non-repeating characters.

Java Code

class Main {
    public static int firstNonRepeating(String str)
    {
        int[] fi
            = new int[256]; 
        for (int i = 0; i < 256; i++)
            fi[i] = -1;

        for (int i = 0; i < str.length(); i++) {
            if (fi[str.charAt(i)] == -1) {
                fi[str.charAt(i)] = i;
            }
            else {
                fi[str.charAt(i)] = -2;
            }
        }

        int res = Integer.MAX_VALUE;

        for (int i = 0; i < 256; i++) {
            if (fi[i] >= 0)
                res = Math.min(res, fi[i]);
        }
        if (res == Integer.MAX_VALUE)
            return -1;
        else
            return res;
    }

    public static void main(String args[])
    {
        String str;
        str = "prepbytes";
        int firstIndex = firstNonRepeating(str);
        if (firstIndex == -1)
            System.out.println(
                "Either all characters are repeating or string is empty");
        else
            System.out.println(
                "First non-repeating character is "
                + str.charAt(firstIndex));
    }
}

Output

First non-repeating character is r 

Time complexity : O(N)
Space complexity : O(1)

Conclusion
In this article, we looked at several Java techniques for locating the first non-repeating character in a string. Among the techniques covered are brute force, indexOf(), hashmaps with two traversals, hashmaps with a single traversal, and sorting. Each method takes a different approach and has different efficiency considerations. By comprehending these methods, programmers can choose the most suitable solution based on the specific requirements of their problem.

Frequently Asked Questions (FAQs)

Q1.In Java, which method is the most efficient for locating the first non-repeating character in a string?
In general, the hashmap approach with a single traversal is the most efficient method, allowing us to find the first non-repeating character in linear time complexity O(N) and constant space complexity O(256).

Q2.Can the hashmap methods handle strings that contain uppercase letters or special characters?
Yes, the hashmap method can deal with strings that contain uppercase letters or special characters. Regardless of case or special characters, they consider each character individually and track their frequencies.

Q3.What is the benefit of using the indexOf() function over other methods?
The indexOf() function method is advantageous because it searches for the current character beginning with its first occurrence in the string. This avoids having to loop through the entire string and may provide a faster solution for locating the first non-repeating character.

Q4.When using the sorting approach, are there any limitations or edge cases to consider?
One drawback of the sorting method is that it necessitates modifying the original string or employing additional data structures. Furthermore, the sorting method assumes a fixed character set of 256 characters. If the character set differs from or exceeds 256, the approach must be modified.

Q5.How can I adapt these methods to locate the first non-repeating character in a case-sensitive string?
You can use the hashmap approach to find the first non-repeating character in a case-sensitive string by treating uppercase and lowercase versions of characters as separate entities. This can be accomplished by converting the string or characters before processing to a consistent case (lowercase or uppercase) or by using a larger character set in the hashmap.