Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Character Bitmask
DSA

Character Bitmask

Learn how bitmasks can compactly represent character sets and support fast string operations.

Character Bitmasking uses bits to represent characters or their frequency parity.

One integer tracks every distinct letter of “banana” — and catches duplicates with a single AND:

Character Bitmask / Duplicate Check

Track distinct letters of a string in a single integer bitmask.

Bit position = letter (ch−'a'); set it with OR, test duplicates with AND. The same letter always maps to the same bit, so revisiting it is detected with one AND and no hash set. O(n) time, O(1) space for a fixed alphabet.

ARRAY VISUALIZER
Steps –
b
0
a
1
n
2
a
3
n
4
a
5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        mask = 0
                      
                        2
                        for ch in string:
                      
                        3
                          bit = 1 << (ch - 'a')
                      
                        4
                          if mask & bit: duplicate found
                      
                        5
                          mask |= bit

For lowercase letters:

'a' → bit 0
'b' → bit 1
'c' → bit 2
...
'z' → bit 25

The key idea:

Character → bit position → use OR for presence and XOR for odd/even frequency.

Recognition Cheat Sheet

If you see…Think…
Lowercase letters onlyCharacter bitmask
Check if character existsOR + AND
Odd/even frequencyXOR
Can form palindromeAt most one odd frequency
Generate character subsetsBitmask enumeration

Main Trigger

Small fixed character set + presence/frequency/parity → Think Bitmask.

1. Character → Bit

The basic conversion:

int bit = 1 << (c - 'a');

Example:

'a' → 1 << 0 → 000001
'b' → 1 << 1 → 000010
'c' → 1 << 2 → 000100

Start with:

int mask = 0;

2. Track Character Existence

Use OR to turn a character’s bit ON.

Java Code

public int buildMask(String s) {
    int mask = 0;

    for (char c : s.toCharArray()) {
        mask |= 1 << (c - 'a');
    }

    return mask;
}
def build_mask(s):
    mask = 0

    for c in s:
        mask |= 1 << (ord(c) - ord('a'))

    return mask
int buildMask(string s) {
    int mask = 0;

    for (char c : s) {
        mask |= 1 << (c - 'a');
    }

    return mask;
}
function buildMask(s) {
  let mask = 0;

  for (const c of s) {
    mask |= 1 << (c.charCodeAt(0) - 97);
  }

  return mask;
}

If a character appears multiple times, its bit simply stays 1.

Recognition

“Which characters are present?” → OR mask

3. Check if Character Exists

Java Code

public boolean containsChar(int mask, char c) {
    int bit = 1 << (c - 'a');
    return (mask & bit) != 0;
}
def contains_char(mask, c):
    bit = 1 << (ord(c) - ord('a'))
    return (mask & bit) != 0
bool containsChar(int mask, char c) {
    int bit = 1 << (c - 'a');
    return (mask & bit) != 0;
}
function containsChar(mask, c) {
  const bit = 1 << (c.charCodeAt(0) - 97);
  return (mask & bit) !== 0;
}

Pattern

Character
   ↓
1 << (c - 'a')
   ↓
AND with mask
   ↓
Present / Not present

Recognition

“Does this character exist?” → AND

4. Track Odd / Even Frequency

This is one of the most useful string bitmask patterns.

Use XOR:

public int frequencyParityMask(String s) {
    int mask = 0;

    for (char c : s.toCharArray()) {
        mask ^= 1 << (c - 'a');
    }

    return mask;
}
def frequency_parity_mask(s):
    mask = 0

    for c in s:
        mask ^= 1 << (ord(c) - ord('a'))

    return mask
int frequencyParityMask(string s) {
    int mask = 0;

    for (char c : s) {
        mask ^= 1 << (c - 'a');
    }

    return mask;
}
function frequencyParityMask(s) {
  let mask = 0;

  for (const c of s) {
    mask ^= 1 << (c.charCodeAt(0) - 97);
  }

  return mask;
}

Every occurrence toggles the bit:

1st occurrence → 1
2nd occurrence → 0
3rd occurrence → 1
4th occurrence → 0

So:

bit = 1 → odd frequency
bit = 0 → even frequency

Recognition

“Odd/even frequency” → XOR

5. Can Form a Palindrome?

A string can be rearranged into a palindrome if at most one character has an odd frequency.

We can track odd frequencies with XOR.

Java Code

public boolean canFormPalindrome(String s) {
    int mask = 0;

    for (char c : s.toCharArray()) {
        mask ^= 1 << (c - 'a');
    }

    return (mask & (mask - 1)) == 0;
}
def can_form_palindrome(s):
    mask = 0

    for c in s:
        mask ^= 1 << (ord(c) - ord('a'))

    return (mask & (mask - 1)) == 0
bool canFormPalindrome(string s) {
    int mask = 0;

    for (char c : s) {
        mask ^= 1 << (c - 'a');
    }

    return (mask & (mask - 1)) == 0;
}
function canFormPalindrome(s) {
  let mask = 0;

  for (const c of s) {
    mask ^= 1 << (c.charCodeAt(0) - 97);
  }

  return (mask & (mask - 1)) === 0;
}

Why?

mask & (mask - 1)

removes the lowest set bit.

Therefore it is 0 when the mask has:

0 set bits → all frequencies even
1 set bit  → exactly one odd frequency

Recognition

“Can rearrange into palindrome?” → XOR frequency mask + at most one set bit

6. Generate Character Subsets

If the string has n characters, there are:

2^n

possible subsets.

Each bit decides whether a character is included.

Java Code

public List<String> charSubsets(String s) {
    int n = s.length();
    List<String> result = new ArrayList<>();

    for (int mask = 0; mask < (1 << n); mask++) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sb.append(s.charAt(i));
            }
        }

        result.add(sb.toString());
    }

    return result;
}
def char_subsets(s):
    n = len(s)
    result = []

    for mask in range(1 << n):
        subset = []

        for i in range(n):
            if mask & (1 << i):
                subset.append(s[i])

        result.append(''.join(subset))

    return result
vector<string> charSubsets(string s) {
    int n = s.size();
    vector<string> result;

    for (int mask = 0; mask < (1 << n); mask++) {
        string sub;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                sub += s[i];
            }
        }

        result.push_back(sub);
    }

    return result;
}
function charSubsets(s) {
  const n = s.length;
  const result = [];

  for (let mask = 0; mask < (1 << n); mask++) {
    let sub = '';

    for (let i = 0; i < n; i++) {
      if ((mask & (1 << i)) !== 0) {
        sub += s[i];
      }
    }

    result.push(sub);
  }

  return result;
}

Recognition

“Generate all subsets” → Enumerate 0 to (1 << n) - 1

Pattern Evolution

Character
    ↓
Map character → bit
    ↓
Existence → OR
    ↓
Check → AND
    ↓
Frequency parity → XOR
    ↓
Palindrome → count/check set bits
    ↓
Subsets → enumerate masks

Visual Example

For:

"aba"

Track parity with XOR:

'a' → 001
'b' → 010
'a' → 001

XOR:

001
010
001
---
010

Final mask:

010

Only b has an odd frequency.

a → 2 times → even
b → 1 time  → odd

So "aba" can form a palindrome.

Common Mistakes

1. Using OR for frequency parity

Wrong:

mask |= 1 << (c - 'a');

OR only tells you whether the character exists.

For odd/even frequency use:

mask ^= 1 << (c - 'a');

2. Forgetting parentheses

Use:

1 << (c - 'a')

not:

1 << c - 'a'

3. Using bitmask for a large character set

A simple int works nicely for:

'a' to 'z' → 26 characters

For larger character sets, use another representation such as a frequency array or multiple masks.

Interview Rule

Character presence → OR Character check → AND Odd/even frequency → XOR Palindrome → at most one odd bit Character subsets → enumerate masks

The main pattern:

int bit = 1 << (c - 'a');

Then choose:

OR  → presence
AND → check
XOR → frequency parity

My Private Notes

Notes are auto-saved locally to this device.