How to Find the First Non-Repeating Character in a String in Java

etd_admin,

Finding the first non-repeating character in a string is a common problem in Java interviews and coding challenges. This task requires analyzing the string to identify the first character that does not appear more than once. In this article, we will explore a simple and efficient way on how to find the first non-repeating character in a string using Java. The solution will be clear and concise, supported by code examples.

Given a string, the goal is to find the first non-repeating character. For example:

  • Input: "swiss"
  • Output: 'w' (as 'w' is the first character that does not repeat)

To find the first non-repeating character in a string in Java, we can use a combination of:

  1. A HashMap to store the frequency of each character.
  2. A single traversal to identify the first character with a frequency of one.
import java.util.HashMap;

public class FirstNonRepeatingCharacter {
    public static char findFirstNonRepeatingChar(String str) {
        if (str == null || str.isEmpty()) {
            throw new IllegalArgumentException("Input string must not be null or empty");
        }

        // Step 1: Count the frequency of each character
        HashMap<Character, Integer> charCountMap = new HashMap<>();
        for (char c : str.toCharArray()) {
            charCountMap.put(c, charCountMap.getOrDefault(c, 0) + 1);
        }

        // Step 2: Find the first character with a frequency of 1
        for (char c : str.toCharArray()) {
            if (charCountMap.get(c) == 1) {
                return c;
            }
        }

        // If no non-repeating character is found
        throw new RuntimeException("No non-repeating character found in the string");
    }

    public static void main(String[] args) {
        String input = "swiss";
        try {
            char result = findFirstNonRepeatingChar(input);
            System.out.println("The first non-repeating character is: " + result);
        } catch (RuntimeException e) {
            System.out.println(e.getMessage());
        }
    }
}

Counting Character Frequencies:
The HashMap stores characters as keys and their frequencies as values.
Example for "swiss":

{s=3, w=1, i=1}

Identifying the First Non-Repeating Character:
By iterating through the string a second time, we can check the HashMap for a character with a frequency of 1. The first such character is returned.

Edge Cases:

  • If the string is null or empty, the method throws an IllegalArgumentException.
  • If all characters repeat, a RuntimeException is thrown.

Alternative Approach: Using Arrays for Fixed Character Set

If the input string contains only lowercase English letters, an array of size 26 can replace the HashMap. This reduces space usage and simplifies implementation:

public static char findFirstNonRepeatingCharUsingArray(String str) {
    if (str == null || str.isEmpty()) {
        throw new IllegalArgumentException("Input string must not be null or empty");
    }

    int[] charCounts = new int[26]; // Array for lowercase English letters
    for (char c : str.toCharArray()) {
        charCounts[c - 'a']++;
    }

    for (char c : str.toCharArray()) {
        if (charCounts[c - 'a'] == 1) {
            return c;
        }
    }

    throw new RuntimeException("No non-repeating character found in the string");
}

In this article, we have learned how to find the first non-repeating character in a string in Java. We used a HashMap for a flexible and efficient solution and explored an alternative approach using arrays for strings with fixed character sets. This problem demonstrates the importance of understanding data structures like HashMap and their applications in solving real-world coding challenges.

Java