Find First Non Repeating Character - Java Program With Time and Space Complexity

Problem Statement
Given a string: "swiss"
Find the first character that appears only once.
Expected Output : w
Because:
s repeats
w appears once and comes first

Solution:
Best Approach (Using LinkedHashMap)
We will use: LinkedHashMap
Why? Because:

• Stores frequency count
• Maintains insertion order

Approach-1 : Frequency Array (int[256])

// Method to find the first non-repeating character
public class FirstNonRepeatingCharacter {
   public static Character firstNonRepeating(final String str) {
         // Check if string is null or empty
        // If yes, return null because no character exists
       if (str == null || str.isEmpty()){
            return null;
        }
        // Create frequency array of size 256
        // Each index represents an ASCII character
        // Example: freq['a'] stores count of 'a'
       int[] freq = new int[256];
       // Convert string into char array and iterate each character
       for(char ch : str.toCharArray()) {
           // Increment frequency count of character
           freq[ch]++;
       }
       // Iterate again to preserve original order
       // We need FIRST non-repeating character
       for(char ch : str.toCharArray()) {
          // Check if character frequency is exactly 1
          if(freq[ch] == 1) {
             // Return first unique character immediately
             return ch;
          }
       }
   // If no non-repeating character found
   return null;
   }
   public static void main(String[] args) {
        // Example 1
        // swiss
        // s -> 3
        // w -> 1
        // i -> 1
        // First non-repeating = w
        System.out.println(firstNonRepeating("swiss"));
        // Example 2
        // null input
        // returns null
        System.out.println(firstNonRepeating(null));
    }
}

Approach-2 : LinkedHashMap

public class FirstNonRepeatingCharacter {

    public static Character findFirstNonRepeating(final String str) {
        if (str == null || str.isEmpty()){
            return null;
        }
        // Step 1: Create LinkedHashMap to store character frequencies
        Map<Character, Integer> map = new LinkedHashMap<>();
        // Step 2: Count frequency of each character
        for(char ch : str.toCharArray()) {
        //If key exists → return value otherwise return default   
       //value 0, for first time of each character always map.getOrDefault(ch, 0) = 0
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        // Step 3: Find first character with frequency 1
        for(Map.Entry<Character, Integer> entry : map.entrySet()) {
            if(entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return null;
    }
   public static void main(String[] args) {
        System.out.println(firstNonRepeating("swiss"));
        System.out.println(firstNonRepeating(null));
    }
}

Approach-3 : Java Streams + groupingBy

public class FirstNonRepeatingCharacter {
    public static char firstNonRepeating(final String str) {
       if (str == null || str.isEmpty()){
            return null;
        }
       Map<Character, Long> map =
            str.chars()
             .mapToObj(c -> (char) c)
             .collect(Collectors.groupingBy(
                     c -> c,
                     LinkedHashMap::new,
                     Collectors.counting()
             ));

       return map.entrySet()
              .stream()
              .filter(e -> e.getValue() == 1)
              .map(Map.Entry::getKey)
              .findFirst()
              .orElse(null);
}
    public static void main(String[] args) {
        System.out.println(firstNonRepeating("swiss"));
        System.out.println(firstNonRepeating(null));
    }
}

Comparing 3 Approaches for First Non-Repeating Character

We will compare:

1. Frequency Array (int[256])
2. LinkedHashMap
3. Java Streams + groupingBy

We’ll analyze:

• readability
• performance
• memory usage
• Unicode support
• interview suitability
• production suitability
• Problem Statement

Input: "swiss"
Frequency:
s -> 3
w -> 1
i -> 1

Output: w
Approach 1 — Frequency Array (int[256])
Code Logic
int[] freq = new int[256];
Store frequency using ASCII index.
Example: freq['s']
stores count of s. Visual Flow "swiss"
↓
freq['s'] = 3
freq['w'] = 1
freq['i'] = 1
Second loop:
s -> 3 ❌
w -> 1 ✅
Return: w
Time Complexity Two loops: O(n) + O(n)
Final: O(n)
Space Complexity int[256]
Fixed size, so: O(1) (constant space)
Advantages
✅ Fastest approach
✅ Lowest memory usage
✅ Very interview-friendly
✅ Excellent cache locality
✅ No object creation overhead
Disadvantages
❌ ASCII only
❌ Not Unicode-safe
❌ Less flexible
❌ Hardcoded size assumption
Important Unicode Problem
This breaks for:

• Chinese
• Japanese
• Emoji
• Unicode chars

Because Unicode exceeds 256.
Best Use Case Best for:

• competitive programming
• ASCII-only systems
• performance-critical code

Approach 2 — LinkedHashMap
Code Logic
Map<Character, Integer> map = new LinkedHashMap<>();

Why LinkedHashMap? Preserves insertion order

Needed for: FIRST non-repeating character
Time Complexity Insertion: O(1) for each char.

Total: O(n) Space Complexity
Worst case: all unique characters
Map stores all. So: O(n)
Advantages
✅ Unicode-safe
✅ Easy to understand
✅ Flexible
✅ Maintains insertion order
✅ Production-friendly

Disadvantages
❌ More memory usage
❌ Object overhead
❌ HashMap node overhead
❌ Slightly slower than array

Internal Memory Cost Each entry stores:

• Character object
• Integer object
• Node object
• next pointer
• hash

Much heavier than array.
Best Use Case
Best for:

• enterprise applications
• Unicode support
• maintainable code
• real production systems

Approach 3 — Streams + groupingBy
Code Logic str.chars()
Convert string to stream. Then: groupingBy(...)
creates frequency map.
Visual Flow
"swiss"
↓ chars()
115 119 105 115 115
↓ mapToObj()
[s,w,i,s,s]
↓ groupingBy()
{
s=3,
w=1,
i=1
}
↓ filter(value == 1)
w
Time Complexity Still: O(n)
BUT Important Hidden Cost

• Streams introduce:
• lambda calls
• boxing/unboxing
• stream pipeline overhead
• temporary objects

So practical runtime is slower. Space Complexity

Internally creates:

• Stream objects
• Collectors
• Lambda instances
• LinkedHashMap

Worst case: O(n)
but with higher constant factors.
Advantages
✅ Elegant
✅ Functional style
✅ Modern Java
✅ Very expressive
✅ Concise

Disadvantages
❌ Slowest approach
❌ More garbage objects
❌ Higher memory overhead
❌ Harder debugging
❌ Less beginner-friendly

Performance Reality Even though all are: O(n)
Big difference exists in actual runtime.
Real Runtime Ranking **
Array > LinkedHashMap > Streams
**Memory Ranking Least memory → Highest memory
Array > LinkedHashMap > Streams
Readability Ranking
Most readable: LinkedHashMap
Most concise: Streams
Most low-level: Array

DRY RUN WITH APPROACH 2(LinkedHashMap) with input swiss
Step 1 — Null/Empty Check

if (str == null || str.isEmpty())

Input: "swiss"
Condition: false
Continue execution.
Step 2 — Create LinkedHashMap

Map<Character, Integer> map = new LinkedHashMap<>();

Initially: {} (empty map)
IMPORTANT
LinkedHashMap preserves insertion order. This is critical.
Step 3 — Convert String to char[]
str.toCharArray()
Result: [s, w, i, s, s]
FIRST LOOP — Count Frequencies
Iteration 1 char ch = 's'
Execute map.getOrDefault('s', 0)
's' not present.
Returns: 0 Then 0 + 1 becomes: 1
Put into map

map.put('s', 1)

Map Now
{
s=1
}
Visual Representation
Head
↓
[s=1]
Iteration 2
char ch = 'w'
Execute
map.getOrDefault('w', 0)
'w' absent.
Returns: 0
Put
map.put('w', 1)

Map Now
{
  s=1,
  w=1
}
Visual
Head
 ↓
[s=1] ⇄ [w=1]

Iteration 3
char ch = 'i'
Execute

map.getOrDefault('i', 0)

Returns: 0
Put

map.put('i', 1)
Map Now
{
  s=1,
  w=1,
  i=1
}

Visual
[s=1] ⇄ [w=1] ⇄ [i=1]
Iteration 4 char ch = 's'
Execute

map.getOrDefault('s', 0)

's' exists. Returns: 1
Increment
1 + 1 = 2
Update Map
map.put('s', 2)

Map Now
{
  s=2,
  w=1,
  i=1
}

IMPORTANT

Insertion order remains SAME.
's' does NOT move.
Visual
[s=2] ⇄ [w=1] ⇄ [i=1]
Iteration 5
char ch = 's'
Execute
map.getOrDefault('s', 0)
Returns: 2
Increment
2 + 1 = 3
Update
map.put('s', 3)

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

Final Internal Linked Order
Head
 ↓
[s=3] ⇄ [w=1] ⇄ [i=1]
SECOND LOOP — Find First Non-Repeating
Traverse entrySet()
for(Map.Entry<Character, Integer> entry : map.entrySet())

Traversal order:
s → w → i

because LinkedHashMap preserves insertion order.

Entry 1
s=3
Check
entry.getValue() == 1
Result: false
Continue.
Entry 2
w=1
Check
entry.getValue() == 1
Result: true
Return return 'w'
Final Output w