Non Repeating Character In A String In Java Leetcode Solution

In this article, you will learn how to efficiently find the index of the first non-repeating character in a given string using Java, a common problem encountered in coding challenges like LeetCode. We will explore multiple effective approaches to solve this problem.

Problem Statement

Given a string s, the task is to find the first non-repeating character in it and return its index. If it does not exist, return -1. This problem emphasizes efficient processing of string data and character frequency tracking.

Example

Consider the input string s = "leetcode". The character 'l' appears once at index 0. The character 'e' appears twice at indices 1 and 7. The character 't' appears once at index 2. The character 'c' appears once at index 3. The character 'o' appears once at index 4. The character 'd' appears once at index 5.

The first character that appears only once in the string is 'l', which is at index 0. So, the expected output is 0.

Background & Knowledge Prerequisites

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

• Strings and Characters: How to iterate through a string, access characters by index, and convert strings to character arrays.
• Loops: for loops for iteration.
• HashMaps (java.util.Map): Understanding key-value pairs, adding elements, retrieving elements, and getOrDefault() method.
• Arrays: Basic array declaration and access.

Use Cases

Finding non-repeating characters has practical applications in various domains:

• Data Processing: Identifying unique entries or anomalies in sequential data streams.
• Text Analysis: Extracting unique characters or words in natural language processing tasks.
• Cryptography: Certain cryptographic algorithms might involve analyzing character frequencies or uniqueness.
• Database Indexing: Optimizing search by identifying unique keys or patterns.
• Software Development: Validating input strings, generating unique identifiers, or solving algorithmic puzzles.

Solution Approaches

We will explore two primary approaches to solve this problem: using a HashMap and using a fixed-size integer array. Both methods involve a two-pass iteration over the string for optimal performance.

Approach 1: Using a HashMap for Character Frequencies

This approach leverages a HashMap to store the frequency of each character in the string. It's highly flexible as it can handle any character set (ASCII, Unicode).

• Summary: Iterate through the string once to populate a hash map with character frequencies. Then, iterate through the string a second time, checking the frequency of each character. The first character encountered with a frequency of 1 is the answer.

// First Non-Repeating Character (HashMap)
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner; // Included as per code pattern, though not strictly needed for the core logic of this problem.

public class Main {
    public static void main(String[] args) {
        String s1 = "leetcode";
        System.out.println("String: \\"" + s1 + "\\", First non-repeating char index: " + firstUniqCharHashMap(s1));

        String s2 = "loveleetcode";
        System.out.println("String: \\"" + s2 + "\\", First non-repeating char index: " + firstUniqCharHashMap(s2));

        String s3 = "aabb";
        System.out.println("String: \\"" + s3 + "\\", First non-repeating char index: " + firstUniqCharHashMap(s3));
    }

    public static int firstUniqCharHashMap(String s) {
        // Step 1: Create a HashMap to store character frequencies.
        // Key: character, Value: count of occurrences
        Map<Character, Integer> charCounts = new HashMap<>();

        // Step 2: Iterate through the string to populate the frequency map.
        // For each character, increment its count.
        for (char c : s.toCharArray()) {
            charCounts.put(c, charCounts.getOrDefault(c, 0) + 1);
        }

        // Step 3: Iterate through the string again to find the first character with a count of 1.
        // The order of iteration is crucial here to find the *first* non-repeating character.
        for (int i = 0; i < s.length(); i++) {
            if (charCounts.get(s.charAt(i)) == 1) {
                return i; // Found the first non-repeating character
            }
        }

        // Step 4: If no non-repeating character is found after checking all characters, return -1.
        return -1;
    }
}

Run

• Sample Output:

  String: "leetcode", First non-repeating char index: 0
  String: "loveleetcode", First non-repeating char index: 2
  String: "aabb", First non-repeating char index: -1

• Stepwise Explanation:

1. A HashMap called charCounts is initialized to store characters as keys and their frequencies as integer values.
2. The code iterates through the input string s character by character. For each character, it updates its count in the charCounts map. getOrDefault(c, 0) ensures that if a character is encountered for the first time, its count starts from 0 before incrementing to 1.
3. After populating the charCounts map, the code iterates through the string s again, this time using an index i.
4. In the second loop, for each character at index i, it retrieves its count from the charCounts map.
5. If the count is exactly 1, it means this is the first non-repeating character encountered from the beginning of the string, so its index i is returned.
6. If the loop completes without finding any character with a count of 1, it means all characters repeat, and -1 is returned.

Approach 2: Using an Integer Array for Character Frequencies

This approach is an optimization when dealing with a known, limited character set, such as ASCII characters. Instead of a HashMap, a simple integer array can be used, where array indices correspond to character ASCII values.

• Summary: Initialize an integer array (e.g., of size 256 for extended ASCII) to store character frequencies. Iterate through the string once to populate this array. Then, iterate through the string a second time, using characters' ASCII values as indices to check their frequencies. Return the index of the first character with a frequency of 1.

// First Non-Repeating Character (Array)
import java.util.Scanner; // Included as per code pattern, though not strictly needed for the core logic of this problem.

public class Main {
    public static void main(String[] args) {
        String s1 = "leetcode";
        System.out.println("String: \\"" + s1 + "\\", First non-repeating char index: " + firstUniqCharArray(s1));

        String s2 = "loveleetcode";
        System.out.println("String: \\"" + s2 + "\\", First non-repeating char index: " + firstUniqCharArray(s2));

        String s3 = "aabb";
        System.out.println("String: \\"" + s3 + "\\", First non-repeating char index: " + firstUniqCharArray(s3));
    }

    public static int firstUniqCharArray(String s) {
        // Step 1: Create an integer array to store character frequencies.
        // Array size 256 accommodates all possible extended ASCII characters (0-255).
        int[] charCounts = new int[256];

        // Step 2: Iterate through the string to populate the frequency array.
        // The character's ASCII value is automatically cast to an int and used as the index.
        for (char c : s.toCharArray()) {
            charCounts[c]++;
        }

        // Step 3: Iterate through the string again to find the first character with a count of 1.
        for (int i = 0; i < s.length(); i++) {
            if (charCounts[s.charAt(i)] == 1) {
                return i; // Found the first non-repeating character
            }
        }

        // Step 4: If no non-repeating character is found, return -1.
        return -1;
    }
}

Run

• Sample Output:

  String: "leetcode", First non-repeating char index: 0
  String: "loveleetcode", First non-repeating char index: 2
  String: "aabb", First non-repeating char index: -1

• Stepwise Explanation:

1. An integer array charCounts of size 256 is initialized. Each index corresponds to an ASCII character value, and the value at that index stores its frequency. All elements are initially 0.
2. The code iterates through the input string s. For each character c, its ASCII value is used as an index to increment the corresponding counter in the charCounts array (charCounts[c]++).
3. After populating the charCounts array, the code iterates through the string s a second time using an index i.
4. For each character s.charAt(i), its count is looked up in the charCounts array.
5. If charCounts[s.charAt(i)] is 1, it signifies that this character appeared only once in the entire string and is the first such character encountered in the string's order. Its index i is returned.
6. If the loop finishes without finding any character with a count of 1, -1 is returned.

Conclusion

Finding the first non-repeating character in a string is a common problem that can be efficiently solved using frequency counting. Both the HashMap and array-based approaches provide solutions with optimal time complexity of O(N) where N is the length of the string, as they involve two passes over the string. The space complexity is O(K) where K is the size of the character set (e.g., 256 for ASCII, or the number of unique characters for HashMap). The array approach is generally faster for fixed, small character sets due to direct index access compared to HashMap overhead.

Summary

• The problem requires finding the index of the first character that appears only once in a string.
• HashMap Approach:
• Uses java.util.HashMap to store Character -> Integer (count) pairs.
• First pass populates the map with all character frequencies.
• Second pass iterates the string to find the first character with a count of 1 in the map.
• Flexible for any character set (ASCII, Unicode).
• Array Approach:
• Uses an int[] of size 256 (for extended ASCII) to store frequencies, where index = char_value.
• First pass populates the array with character frequencies.
• Second pass iterates the string to find the first character with a count of 1 in the array.
• Generally faster than HashMap for limited character sets due to direct array access.
• Both approaches offer O(N) time complexity and O(K) space complexity.