Non Repeating Character

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find first non-repeating character in a string. Frequency array + second pass.

Algorithm

1Count frequency of each character. Scan string left to right: return first char with freq == 1.

Common Pitfalls

•Two passes: first count, then find. O(n) time. Return -1 if all repeat.

Non Repeating Character.java

Java

// Approach: Frequency array of size 26. First pass count; second pass find first with frequency 1.
// Time: O(n) Space: O(1)
class Solution {
    // Function to find the first non-repeating character in a string.
    static char nonRepeatingChar(String s) {
        Map<Character, Integer> m = new HashMap();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            m.put(ch, m.getOrDefault(ch, 0) + 1);
        }

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            
            if (m.get(ch) == 1)
                return ch;
        }
        return '$';
    }
}

Was this solution helpful?