One-of-a-Kind Bead

Easyhash mapAlso known as First Unique Character in a String

You make bracelets. Before tying one off, you lay the beads out in a line and write down their colours as letters: r for red, g for green, b for blue, and so on.

Your signature touch is to put the clasp next to a bead whose colour appears nowhere else on that bracelet. If there are several such beads, you pick the one closest to the start.

Your task

Write firstSoloBead(beads). beads is a string of lowercase letters, one per bead. Return the position (index) of the first bead whose letter appears exactly once in the whole string.

If every colour appears at least twice, or the string is empty, return -1.

firstSoloBead(beads: string) → int

Examples

Example 1

Input

beads = "rgrbgy"

Output

Why

Red appears twice and green appears twice. Blue, at position 3, appears once, and so does yellow at position 5. Blue comes first, so the answer is 3.

Example 2

Input

beads = "wkkw"

Output

-1

Why

White and black both appear twice. No bead is one of a kind, so the answer is -1.

Example 3

Input

beads = "ppob"

Output

Why

The answer is 2, not 0. Purple at position 0 has not been repeated yet when you first see it, but it is repeated right after, so it does not count.

Constraints

0 ≤ beads.length ≤ 100,000
beads contains only lowercase letters a to z.

Start with brute force

For each bead, scan the whole string and count how many beads share its colour. Return the first bead whose count is 1.

Every bead triggers a full scan, so this is O(n²). With 100,000 beads that is up to 10 billion letter comparisons, and most of them repeat the same counting work.

Hints

0 of 4 shown

Hint 1
Look at ppob. Standing on the first p, can you already tell whether it is one of a kind? What would you need to know first?
Hint 2
Whether a bead is unique depends on the beads after it too. So you cannot decide in the same pass where you first meet a colour.
Hint 3
Split the work into two passes. What could the first pass record so that the second pass can answer "is this colour unique?" in one step?
Hint 4
First pass: count how many beads of each colour there are, in a map or an array of 26 counters. Second pass: walk from the start and return the first position whose colour has a count of exactly 1. If none does, return -1.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The brute force recounts a colour every time it meets a bead. Count every colour once up front, and each question becomes a single lookup.

Trace rgrbgy:

First pass, counting: r → 2, g → 2, b → 1, y → 1.
Second pass. Position 0 is r, count 2: skip.
Position 1 is g, count 2: skip. Position 2 is r: skip.
Position 3 is b, count 1. Return 3.

The common mistake is to decide in a single pass: "I have not seen this colour before, so it must be unique." That answers 0 for ppob, because the second p has not been read yet. A colour is unique only once you have seen the whole bracelet.

Reference solution

function firstSoloBead(beads) {
  const count = new Map(); // colour -> number of beads
  for (const c of beads) count.set(c, (count.get(c) || 0) + 1);
  for (let i = 0; i < beads.length; i++) {
    if (count.get(beads[i]) === 1) return i; // first one-of-a-kind
  }
  return -1;
}

def first_solo_bead(beads):
    count = {}  # colour -> number of beads
    for c in beads:
        count[c] = count.get(c, 0) + 1
    for i, c in enumerate(beads):
        if count[c] == 1:  # first one-of-a-kind
            return i
    return -1

TimeO(n)Two passes over the string, with O(1) map work per bead.

SpaceO(1)The map holds at most 26 colours, however long the bracelet is.

Learn the idea: Hash Tables Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code