First Letter to Appear Twice

easy bit manipulation bitmask string

Problem

Given a string s of lowercase English letters, return the first letter to appear twice. Letter a counts as appearing twice before letter b if the second occurrence of a comes before the second occurrence of b. Scanning left to right, the answer is simply the first character we land on that we have already seen.

Inputs = "abccbaacz"

Output"c"

At index 3 we read 'c', which already appeared at index 2. Its second occurrence is earlier than any other letter's, so 'c' is returned.

s (lowercase letters)

def repeatedCharacter(s):
    seen = 0                       # 26-bit mask of letters seen
    for ch in s:
        bit = 1 << (ord(ch) - ord('a'))
        if seen & bit:             # bit already set -> repeat
            return ch
        seen |= bit                # mark this letter as seen
    return ''                      # unreachable by constraints

function repeatedCharacter(s) {
  let seen = 0;                       // 26-bit mask of letters seen
  for (const ch of s) {
    const bit = 1 << (ch.charCodeAt(0) - 97);
    if (seen & bit) {                 // bit already set -> repeat
      return ch;
    }
    seen |= bit;                      // mark this letter as seen
  }
  return '';                          // unreachable by constraints
}

char repeatedCharacter(String s) {
    int seen = 0;                       // 26-bit mask of letters seen
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        int bit = 1 << (ch - 'a');
        if ((seen & bit) != 0) {        // bit already set -> repeat
            return ch;
        }
        seen |= bit;                    // mark this letter as seen
    }
    return ' ';                         // unreachable by constraints
}

char repeatedCharacter(string s) {
    int seen = 0;                       // 26-bit mask of letters seen
    for (char ch : s) {
        int bit = 1 << (ch - 'a');
        if (seen & bit) {              // bit already set -> repeat
            return ch;
        }
        seen |= bit;                    // mark this letter as seen
    }
    return ' ';                         // unreachable by constraints
}

Explanation

We only need one left-to-right pass. The first character that we have already encountered is exactly the letter whose second occurrence comes earliest, which is what the problem asks for.

To remember which letters we have seen, we use a 26-bit integer as a set instead of a hash set or a boolean array. Each lowercase letter maps to one bit: 'a' → bit 0, 'b' → bit 1, and so on. For a character ch the bit position is ord(ch) - ord('a'), and the single-bit value is bit = 1 << position.

For each character we test membership with the bitwise AND: seen & bit. If that result is non-zero the bit is already set, meaning this letter appeared before, so we return it immediately. Otherwise we add the letter to the set with the bitwise OR assignment seen |= bit, which turns that one bit on without disturbing the others.

Example walk-through on "abccbaacz": 'a' sets bit 0, 'b' sets bit 1, the first 'c' sets bit 2. The very next character is 'c' again — its bit is already on, so the AND is non-zero and we return 'c' at index 3, before ever reaching the later repeats of 'a'.

The bitmask makes each membership test and insertion a single machine-word operation, and the whole "set" is just one int. The constraints guarantee at least one repeat, so the trailing return is never reached.

Time: O(n) Space: O(1)