Non Repeating Character In A String In Java 8

Finding the first non-repeating character in a string is a common programming challenge that tests understanding of string manipulation and data structures. It's a useful skill for tasks involving data validation, text processing, and algorithm design. In this article, you will learn several effective ways to solve this problem in Java, including traditional iterative methods and modern Java 8 Stream API approaches.

Problem Statement

The core problem involves identifying the character in a given string that appears only once, and whose first occurrence is earlier than any other non-repeating character. If no such character exists (e.g., all characters repeat, or the string is empty), the solution should indicate this, typically by returning a special character or an empty Optional.

Example

Consider the input string "swiss".

• 's' appears twice.
• 'w' appears once.
• 'i' appears once.

The first character encountered that doesn't repeat is 'w'. If the string was "teeter", the 'r' would be the first non-repeating character.

Background & Knowledge Prerequisites

To effectively understand the solutions presented, a basic grasp of the following Java concepts is beneficial:

• String Basics: Understanding how strings work in Java, including charAt(), length(), and character iteration.
• Data Structures: Familiarity with HashMap (for key-value pairs) and LinkedHashMap (for maintaining insertion order).
• Collections Framework: Basic knowledge of iterating through collections.
• Java 8 Streams: Understanding Stream operations like mapToObj, collect, filter, findFirst, groupingBy, and counting.

Use Cases or Case Studies

This problem, while seemingly simple, has practical applications in various domains:

• Data Validation: Identifying unique characters in user input (e.g., ensuring a password contains at least one unique special character).
• Log Analysis: Finding the first unique identifier or event code in a stream of log entries.
• Text Processing: In natural language processing, finding unique characters can be a step in tokenization or character frequency analysis.
• Caching Mechanisms: Determining the "least recently used" character in a cache-like scenario (though often more complex algorithms are used).
• Unique ID Generation: As a building block for creating unique identifiers based on input strings.

Solution Approaches

Here, we will explore three distinct approaches to solve the problem, each with its own advantages regarding performance and readability.

Approach 1: Using LinkedHashMap

This approach leverages the LinkedHashMap to maintain the order of character insertion while also tracking their frequencies.

• One-line summary: Iterate through the string, store character counts in a LinkedHashMap to preserve insertion order, then iterate the map to find the first character with a count of one.

// First Non-Repeating Character using LinkedHashMap
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Optional;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        String input1 = "swiss";
        String input2 = "teeter";
        String input3 = "aabbcc";
        String input4 = "java";
        String input5 = "";

        System.out.println("Input: \\"" + input1 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharLinkedHashMap(input1).orElse(' '));
        System.out.println("Input: \\"" + input2 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharLinkedHashMap(input2).orElse(' '));
        System.out.println("Input: \\"" + input3 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharLinkedHashMap(input3).orElse(' '));
        System.out.println("Input: \\"" + input4 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharLinkedHashMap(input4).orElse(' '));
        System.out.println("Input: \\"" + input5 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharLinkedHashMap(input5).orElse(' '));
    }

    public static Optional<Character> findFirstNonRepeatingCharLinkedHashMap(String str) {
        // Step 1: Handle null or empty string
        if (str == null || str.isEmpty()) {
            return Optional.empty();
        }

        // Step 2: Use LinkedHashMap to store character counts and maintain insertion order
        Map<Character, Integer> charCounts = new LinkedHashMap<>();
        for (char c : str.toCharArray()) {
            charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
        }

        // Step 3: Iterate through the LinkedHashMap to find the first character with a count of 1
        for (Map.Entry<Character, Integer> entry : charCounts.entrySet()) {
            if (entry.getValue() == 1) {
                return Optional.of(entry.getKey());
            }
        }

        // Step 4: If no non-repeating character is found
        return Optional.empty();
    }
}

Run

• Sample output:

Input: "swiss" -> First non-repeating character: w
Input: "teeter" -> First non-repeating character: r
Input: "aabbcc" -> First non-repeating character:  
Input: "java" -> First non-repeating character: j
Input: "" -> First non-repeating character:

• Stepwise explanation:

1. Handle Edge Cases: Check if the input string is null or empty. If so, return an empty Optional.
2. Populate LinkedHashMap: Iterate over each character in the input string. For each character, store its count in a LinkedHashMap. LinkedHashMap is crucial here because it preserves the order in which characters were first encountered.
3. Find First Non-Repeating: Iterate through the entrySet() of the LinkedHashMap. The first entry whose value (character count) is 1 represents the first non-repeating character in the original string. Return it wrapped in an Optional.
4. No Non-Repeating Character: If the loop completes without finding any character with a count of 1, it means all characters repeat, or the string was empty (handled in step 1). Return an empty Optional.

Approach 2: Using Java 8 Stream API

This approach provides a more concise and functional way to achieve the same result using Java 8 Streams.

• One-line summary: Stream the string's characters, group them by identity to count occurrences, then filter for characters with a count of one and find the first such character, all while preserving insertion order using LinkedHashMap in the grouping collector.

// First Non-Repeating Character using Java 8 Stream API
import java.util.LinkedHashMap;
import java.util.Optional;
import java.util.function.Function;
import java.util.stream.Collectors;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        String input1 = "swiss";
        String input2 = "teeter";
        String input3 = "aabbcc";
        String input4 = "java";
        String input5 = "";

        System.out.println("Input: \\"" + input1 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharStream(input1).orElse(' '));
        System.out.println("Input: \\"" + input2 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharStream(input2).orElse(' '));
        System.out.println("Input: \\"" + input3 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharStream(input3).orElse(' '));
        System.out.println("Input: \\"" + input4 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharStream(input4).orElse(' '));
        System.out.println("Input: \\"" + input5 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharStream(input5).orElse(' '));
    }

    public static Optional<Character> findFirstNonRepeatingCharStream(String str) {
        // Step 1: Handle null or empty string
        if (str == null || str.isEmpty()) {
            return Optional.empty();
        }

        // Step 2: Stream characters, group them by identity, count occurrences,
        // and collect into a LinkedHashMap to preserve order.
        Map<Character, Long> charCounts = str.chars()
                .mapToObj(c -> (char) c)
                .collect(Collectors.groupingBy(
                        Function.identity(),
                        LinkedHashMap::new, // This ensures insertion order is preserved
                        Collectors.counting()
                ));

        // Step 3: Stream the entries of the charCounts map, filter for count 1, and find the first character
        return charCounts.entrySet().stream()
                .filter(entry -> entry.getValue() == 1)
                .map(Map.Entry::getKey)
                .findFirst();
    }
}

Run

• Sample output:

Input: "swiss" -> First non-repeating character: w
Input: "teeter" -> First non-repeating character: r
Input: "aabbcc" -> First non-repeating character:  
Input: "java" -> First non-repeating character: j
Input: "" -> First non-repeating character:

• Stepwise explanation:

1. Handle Edge Cases: Similar to the previous approach, check for null or empty strings.
2. Stream and Count:

• str.chars() creates an IntStream of character ASCII values.
• mapToObj(c -> (char) c) converts the IntStream to a Stream.
• collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting())) is the core.
• Function.identity() means grouping by the character itself.
• LinkedHashMap::new specifies that the map used for grouping should be a LinkedHashMap, which maintains insertion order. This is crucial for correctly identifying the *first* non-repeating character based on its original position.
• Collectors.counting() aggregates the counts for each character.

1. Find First Non-Repeating:

• charCounts.entrySet().stream() creates a stream of map entries.
• filter(entry -> entry.getValue() == 1) keeps only those entries where the character count is one.
• map(Map.Entry::getKey) extracts the character key from the filtered entries.
• findFirst() returns an Optional containing the first character found that satisfies the criteria.

Approach 3: Using Frequency Array (for ASCII characters)

For strings consisting solely of ASCII characters, an array can be an extremely efficient way to store frequencies, avoiding the overhead of HashMap objects.

• One-line summary: Use a simple integer array to store character counts, then iterate through the string again to find the first character whose count in the array is one.

// First Non-Repeating Character using Frequency Array
import java.util.Optional;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        String input1 = "swiss";
        String input2 = "teeter";
        String input3 = "aabbcc";
        String input4 = "java";
        String input5 = "";
        String input6 = "abacaba"; // Example with repeating but first unique char

        System.out.println("Input: \\"" + input1 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharFrequencyArray(input1).orElse(' '));
        System.out.println("Input: \\"" + input2 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharFrequencyArray(input2).orElse(' '));
        System.out.println("Input: \\"" + input3 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharFrequencyArray(input3).orElse(' '));
        System.out.println("Input: \\"" + input4 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharFrequencyArray(input4).orElse(' '));
        System.out.println("Input: \\"" + input5 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharFrequencyArray(input5).orElse(' '));
        System.out.println("Input: \\"" + input6 + "\\" -> First non-repeating character: " + findFirstNonRepeatingCharFrequencyArray(input6).orElse(' '));
    }

    public static Optional<Character> findFirstNonRepeatingCharFrequencyArray(String str) {
        // Step 1: Handle null or empty string
        if (str == null || str.isEmpty()) {
            return Optional.empty();
        }

        // Step 2: Initialize a frequency array for ASCII characters (0-255)
        int[] charCounts = new int[256]; // Assuming ASCII or extended ASCII

        // Step 3: Populate the frequency array by iterating through the string once
        for (char c : str.toCharArray()) {
            // Ensure character is within array bounds, otherwise handle error or expand array
            if (c < 256) {
                charCounts[c]++;
            } else {
                // Handle non-ASCII characters if necessary, e.g., using a Map instead
                // For simplicity, we'll assume ASCII/extended ASCII for this approach
                System.err.println("Warning: Character out of ASCII range ignored: " + c);
            }
        }

        // Step 4: Iterate through the string again to find the first character with a count of 1
        for (char c : str.toCharArray()) {
            if (c < 256 && charCounts[c] == 1) {
                return Optional.of(c);
            }
        }

        // Step 5: If no non-repeating character is found
        return Optional.empty();
    }
}

Run

• Sample output:

Input: "swiss" -> First non-repeating character: w
Input: "teeter" -> First non-repeating character: r
Input: "aabbcc" -> First non-repeating character:  
Input: "java" -> First non-repeating character: j
Input: "" -> First non-repeating character:  
Input: "abacaba" -> First non-repeating character: c

• Stepwise explanation:

1. Handle Edge Cases: Check for null or empty strings.
2. Initialize Frequency Array: Create an int array of size 256 (for extended ASCII characters). All elements are initialized to 0.
3. Populate Frequencies: Iterate through the input string. For each character c, increment charCounts[c]. This step counts the occurrences of each character.
4. Find First Non-Repeating: Iterate through the input string *again*. This second pass is crucial to ensure we find the *first* non-repeating character according to its original position. The first character c encountered for which charCounts[c] is 1 is the answer.
5. No Non-Repeating Character: If the second loop completes without finding such a character, return an empty Optional.

Conclusion

Finding the first non-repeating character in a string can be approached in several ways, each with its strengths. The LinkedHashMap approach is versatile and works well for all character sets, maintaining insertion order explicitly. The Java 8 Stream API offers a more functional and often more readable solution, especially when combined with LinkedHashMap for order preservation. For strings with limited character sets (like ASCII), the frequency array method provides excellent performance due to direct array access. Choosing the right approach depends on the specific requirements, including performance needs, character set, and code readability preferences.

Summary

• Problem: Find the character that appears only once and is the first to do so in a given string.
• LinkedHashMap Approach:
• Uses LinkedHashMap to store character counts while preserving insertion order.
• Iterates the map to find the first entry with a count of 1.
• Good for general character sets.
• Java 8 Stream API Approach:
• Leverages Collectors.groupingBy with LinkedHashMap::new and Collectors.counting().
• Filters the resulting map entries and uses findFirst() to locate the character.
• Concise and idiomatic for Java 8+.
• Frequency Array Approach:
• Uses an int[] array (e.g., size 256 for ASCII) to store character counts.
• Requires two passes: one to count, one to find the first non-repeating character.
• Highly efficient for fixed, small character sets.
• Best Practices: Handle empty or null strings, choose data structures that preserve order when necessary, and consider character set limitations.