Menu

Earn Premium with Referrals

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

See how it works and start inviting friends.

String Bitmask
DSA

String Bitmask

Learn how bitmasks can efficiently represent character sets and solve string problems involving distinct characters.

A bitmask packs the character set of a string into one integer — bit c - 'a' says whether c is present.

Focus on recognizing:

“Which characters exist” (not how many) + small alphabet → one int instead of a Set

Core Operations

add ch      → mask |= 1 << (ch - 'a')
has ch      → mask & (1 << (ch - 'a')) != 0
common(A,B) → maskA & maskB
union(A,B)  → maskA | maskB
subset      → (sub & super) == sub
distinct    → popcount(mask)

Pattern 1: All Characters Unique

The mask building over "LEETCODE" — bit 4 ('e') is already set when the second E arrives. Press ▶ to animate.

Unique Characters (Bitmask)

Test if a string has all distinct characters using a 26-bit integer mask: one bit per letter. If a character's bit is already set when you reach it, the string repeats.

Input: L E E T C O D E. Walk left to right; for each letter compute its bit (ch - 'a') and check the mask. 'L' and the first 'E' set fresh bits. The second 'E' finds bit 4 already on → duplicate detected and we bail immediately. One integer replaces a HashSet and runs in O(n).

ARRAY VISUALIZER
Steps –
L
0
E
1
E
2
T
3
C
4
O
5
D
6
E
7
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        mask = 0
                      
                        2
                        for ch in s:
                      
                        3
                          bit = 1 << (ch - 'a')
                      
                        4
                          if mask & bit: return false   // already seen
                      
                        5
                          mask |= bit
                      
                        6
                        return true

Set-bit-before-check detects duplicates in one pass:

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

    for (char c : s.toCharArray()) {
        int bit = 1 << (c - 'a');

        if ((mask & bit) != 0)
            return false;          // already seen

        mask |= bit;
    }

    return true;
}
def has_unique_chars(s):
    mask = 0

    for ch in s:
        bit = 1 << (ord(ch) - 97)

        if mask & bit:
            return False       # already seen

        mask |= bit

    return True
bool hasUniqueChars(const string& s) {
    int mask = 0;

    for (char c : s) {
        int bit = 1 << (c - 'a');

        if (mask & bit)
            return false;      // already seen

        mask |= bit;
    }

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

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

    if (mask & bit) return false; // already seen

    mask |= bit;
  }

  return true;
}

Check-then-set with one integer replaces an entire HashSet.

Pattern 2: Common Characters Between Two Strings

private int maskOf(String s) {
    int m = 0;
    for (char c : s.toCharArray())
        m |= 1 << (c - 'a');
    return m;
}

public List<Integer> commonChars(String[] words) {
    // e.g. words containing at least one shared letter:
    List<Integer> result = new ArrayList<>();

    for (int i = 0; i < words.length; i++)
        for (int j = i + 1; j < words.length; j++)
            if ((maskOf(words[i]) & maskOf(words[j])) != 0) {
                result.add(i);
                result.add(j);
            }

    return result;
}
def mask_of(s):
    m = 0
    for ch in s:
        m |= 1 << (ord(ch) - 97)
    return m


def pairs_with_common_char(words):
    masks = [mask_of(w) for w in words]
    return [
        (i, j)
        for i in range(len(words))
        for j in range(i + 1, len(words))
        if masks[i] & masks[j]     # any shared bit
    ]
int maskOf(const string& s) {
    int m = 0;
    for (char c : s)
        m |= 1 << (c - 'a');
    return m;
}

vector<pair<int,int>> pairsWithCommonChar(vector<string>& words) {
    vector<int> masks;
    for (auto& w : words) masks.push_back(maskOf(w));

    vector<pair<int,int>> result;
    for (int i = 0; i < (int)masks.size(); i++)
        for (int j = i + 1; j < (int)masks.size(); j++)
            if (masks[i] & masks[j])   // any shared bit
                result.push_back({i, j});

    return result;
}
const maskOf = (s) => {
  let m = 0;
  for (const c of s) m |= 1 << (c.charCodeAt(0) - 97);
  return m;
};

function pairsWithCommonChar(words) {
  const masks = words.map(maskOf);
  const result = [];

  for (let i = 0; i < masks.length; i++)
    for (let j = i + 1; j < masks.length; j++)
      if (masks[i] & masks[j])
        // any shared bit
        result.push([i, j]);

  return result;
}

AND answers “any character in common” in one instruction — no nested loops over letters.

Pattern 3: Subset Check & Distinct Count

// Is every char of t inside s?
public boolean charsSubset(String t, String s) {
    return (maskOf(t) & ~maskOf(s)) == 0;
}

// How many distinct chars?
public int distinctCount(String s) {
    return Integer.bitCount(maskOf(s));
}
def chars_subset(t, s):
    # Is every char of t inside s?
    return mask_of(t) & ~mask_of(s) == 0


def distinct_count(s):
    return bin(mask_of(s)).count("1")
bool charsSubset(const string& t, const string& s) {
    // Is every char of t inside s?
    return (maskOf(t) & ~maskOf(s)) == 0;
}

int distinctCount(const string& s) {
    return __builtin_popcount(maskOf(s));
}
function charsSubset(t, s) {
  // Is every char of t inside s?
  return (
    (maskOf(t) & ~maskOf(s)) % 4294967296 === 0 ||
    (maskOf(t) & ~maskOf(s)) === 0
  );
}

function distinctCount(s) {
  let m = maskOf(s),
    count = 0;

  while (m) {
    m &= m - 1; // clear lowest set bit
    count++;
  }

  return count;
}

(sub & ~super) == 0 is the cleanest subset test; popcount counts distinct letters.

Common Mistakes

Using bitmask when frequency matters.

A mask stores presence only — "aab" and "ab" have identical masks.

Alphabets larger than the int.

26 lowercase fits int; mixed case needs 52+ bits → use long or two ints.

Forgetting operator precedence.

mask & bit != 0 parses as mask & (bit != 0) in some languages — always parenthesize.

Complexity

OperationTimeSpace
Build maskO(n)O(1)
Compare two stringsO(1) after buildO(1)
UniquenessO(n)O(1)

My Private Notes

Notes are auto-saved locally to this device.