easy Problem 1 First Non-repeating Character

Problem Statement

Given a string, identify the position of the first character that appears only once in the string. If no such character exists, return -1.

Examples

Example 1:
- Input: "apple"
- Expected Output: 0
- Justification: The first character 'a' appears only once in the string and is the first character.
Example 2:
- Input: "abcab"
- Expected Output: 2
- Justification: The first character that appears only once is 'c' and its position is 2.
Example 3:
- Input: "abab"
- Expected Output: -1
- Justification: There is no character in the string that appears only once.

Constraints:

1 <= s.length <= 10⁵
s consists of only lowercase English letters.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — First Non-repeating Character

Why this concept exists (judgment layer)

First unique character index is the textbook two-pass frequency map: count globally, then scan order for count==1. Teaches why one pass cannot know uniqueness without full counts.

Worked example with complexity derivation

"abcab": counts a2 b2 c1; scan a(no) b(no) c(yes) → index 2.
"apple" → a at 0; "abab" → -1.
n≤1e5: O(n) required; nested count per index O(n²) fails.

Pattern + when-NOT / named alternative

PATTERN: FREQUENCY MAP + ORDERED RESCAN for first count==1. WHEN NOT: stream online with LinkedHashMap if one pass required. Sort loses first-occurrence order. Not stack.

Edge case / failure mode

Edges: all unique → 0; all dups → -1; single char; last char unique. Lowercase only.

Hostile-panel drills (defend the decision)

Q1. Why two passes?
Model answer: Uniqueness is global; early index cannot know future repeats without counting first.

Q2. Array[26] vs HashMap?
Model answer: Fixed alphabet → int[26] O(1) space clearer; HashMap generalizes.

Q3. Return char vs index?
Model answer: Problem asks position; same scan, return i or s[i].

✅ Solution First Non-repeating Character

Problem Statement

Given a string, identify the position of the first character that appears only once in the string. If no such character exists, return -1.

Examples

Example 1:
- Input: "apple"
- Expected Output: 0
- Justification: The first character 'a' appears only once in the string and is the first character.
Example 2:
- Input: "abcab"
- Expected Output: 2
- Justification: The first character that appears only once is 'c' and its position is 2.
Example 3:
- Input: "abab"
- Expected Output: -1
- Justification: There is no character in the string that appears only once.

Constraints:

1 <= s.length <= 10⁵
s consists of only lowercase English letters.

Solution

To solve this problem, we'll use a hashmap to keep a record of each character in the string and the number of times it appears. First, iterate through the string and populate the hashmap with each character as the key and its frequency as the value. Then, go through the string again, this time checking each character against the hashmap. The first character that has a frequency of one (indicating it doesn't repeat) is your target. This character is the first non-repeating character in the string. If no such character exists, the solution should indicate that as well. This two-pass approach ensures efficiency, as each character is checked against a pre-compiled frequency map.

Initialization: Begin by creating a hashmap to store the frequency of each character in the string. This hashmap will help in identifying characters that appear only once.
Frequency Count: Traverse the string from the beginning to the end. For each character, increment its count in the hashmap.
First Unique Character: Traverse the string again from the beginning. For each character, check its frequency in the hashmap. If the frequency is 1, return its position as it's the first unique character.
No Unique Character: If the string is traversed completely without finding a unique character, return -1.

Using a hashmap ensures that we can quickly determine the frequency of each character without repeatedly scanning the string.

Algorithm Walkthrough:

Given the input string "abcab":

Initialize a hashmap to store character frequencies.
Traverse the string:
- 'a' -> frequency is 1
- 'b' -> frequency is 1
- 'c' -> frequency is 1
- 'a' -> frequency is 2
- 'b' -> frequency is 2
Traverse the string again:
- 'a' has frequency 2
- 'b' has frequency 2
- 'c' has frequency 1, so return its position 2.

Here is the visual representation of the algorithm:

Code

Here is the code for this algorithm:

java

import java.util.HashMap;

public class Solution {

  public int firstUniqChar(String s) {
    // Create a hashmap to store the frequency of each character
    HashMap<Character, Integer> freq = new HashMap<>();

    // Traverse the string to populate the hashmap with character frequencies
    for (char c : s.toCharArray()) {
      freq.put(c, freq.getOrDefault(c, 0) + 1);
    }

    // Traverse the string again to find the first unique character
    for (int i = 0; i < s.length(); i++) {
      if (freq.get(s.charAt(i)) == 1) {
        return i;
      }
    }

    // If no unique character is found, return -1
    return -1;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.firstUniqChar("apple")); // Expected: 0
    System.out.println(sol.firstUniqChar("abcab")); // Expected: 2
    System.out.println(sol.firstUniqChar("abab")); // Expected: -1
  }
}

Time Complexity

Populating the hashmap with frequencies: We traverse the entire string once to populate the hashmap with the frequency of each character. This operation takes time, where n is the length of the string.
Finding the first unique character: We traverse the string again to find the first character with a frequency of 1. This operation also takes time.

Given that these two operations are sequential and not nested, the overall time complexity is , which simplifies to .

Space Complexity

Hashmap for frequencies: In the worst case, every character in the string is unique. For a string with only lowercase English letters, the maximum number of unique characters is 26. However, if we consider all possible ASCII characters, the number is 128. If we consider extended ASCII, it's 256. In any case, this is a constant number. Therefore, the space complexity for the hashmap is because it doesn't grow proportionally with the size of the input string.
Input string: The space taken by the input string is not counted towards the space complexity, as it's considered input space.

Given the above, the overall space complexity of the algorithm is .

🎯 STRICT STANDOUT: Why / worked+complexity / pattern+when-not / edge / drills — Solution First Non-repeating Character

Why this concept exists (judgment layer)

Solution HashMap count then rescan — correct. Elevation derives Θ(n), space Θ(Σ), and int[26] optimization under lowercase constraint.

Worked example with complexity derivation

"abcab": pass1 {a:2,b:2,c:1}; pass2 i=0,1 skip i=2 c→return 2.
Time 2n map ops → Θ(n); space O(Σ)≤26 here.
Queue alternative: enqueue first-seen, dequeue when count>1 — still O(n) but more code.

Pattern + when-NOT / named alternative

PATTERN: count then left-to-right first unique. WHEN NOT: need last unique → scan right-to-left. Brute per-index recount forbidden at n=1e5.

Edge case / failure mode

Hand-run abab → -1; a → 0; aabbcd → 4 ('c').

Hostile-panel drills (defend the decision)

Q1. Complexity derivation.
Model answer: Θ(n) + Θ(n) scans; HashMap ≤ min(n,Σ) keys → Θ(n) time, O(Σ) space.

Q2. Could one HashMap of first index + count work?
Model answer: Yes: store (count, firstIdx), then min idx among count==1 — still need full counts before decide.

Q3. Why not sort?
Model answer: Sort destroys original indices needed for 'first'.

🧩 Pattern · Hashing

Recognize it: Membership / frequency / “have I seen this?” in O(1) → a hash map or set.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Problem 1 First Non-repeating Character? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Problem 1 First Non-repeating Character** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Problem 1 First Non-repeating Character** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Problem 1 First Non-repeating Character**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Problem 1 First Non-repeating Character**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Word Pattern Problem 2 Largest Unique Number →