Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Akmal Alikhujaev
Bit vector solution O(n) S(1)

Akmal Alikhujaev

Apr 28, 2024

Since there are only 26 letters in English alphabet we can use a bit vector (bit vector is a single 32-bit integer) to map every character to a single bit index like this:

'a' -> 0th bit

'b' -> 1st bit

...

'z' -> 25th bit

While iterating through the string, if the current character is letter, we have to lowercase it (if required) and then we can get its bitIndex by subtracting lowercase 'a' from the character. So we get the following mapping:

'a' - 'a' -> 0

'b' - 'a' -> 1

'c' - 'a' -> 2

....

'z' - 'a' -> 25

That gives us the bit index, which we need to set to 1 (marking the character as present). We can set a particular bit on an integer x using following operation

x = x | (1 << bitIndex);

If you don't know the expression above, I highly suggest to read about bit manipulations and its syntax in your programming language of choice.

So at the end it sufficies to check if our bitVector has all 26 bits set (0th bit to 25th). We can of course go and check every bit in a loop, or we can be a little bit smarter and compare our bitVector to the (1 << 26) - 1

What does it mean? We set bit at index 26 (27th bit) to 1 and subtract 1 from the resulting number, that trick sets bit at index 26 to 0 and sets all bits from indx 25 down to 0 to 1.

class Solution { public boolean checkIfPangram(String sentence) { char letter; int vector = 0; for (int i = 0; i < sentence.length(); i++) { letter = sentence.charAt(i); if (Character.isLetter(letter)) { letter = Character.toLowerCase(letter); vector |= (1 << (letter - 'a')); } } return vector == (1 << 26) - 1; } }

0

0

Comments
Comments

On this page

Problem Statement

Solution

Code

Time Complexity

Space Complexity

Conclusion