Check if the Sentence Is Pangram

Difficulty: Easy | Acceptance: 84.20% | Paid: No Topics: Hash Table, String

A pangram is a sentence where every letter of the English alphabet appears at least once.

Given a string sentence containing only lowercase English letters, return true if sentence is a pangram, or false otherwise.

• Examples
• Constraints
• HashSet
• Boolean Array
• Bit Manipulation

Examples

Example 1:

Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true
Explanation: The sentence contains at least one occurrence of every letter of the English alphabet.

Example 2:

Input: sentence = "leetcode"
Output: false

Constraints

1 <= sentence.length <= 1000
sentence consists of lowercase English letters.

HashSet

Intuition Use a hash set to store unique characters encountered in the sentence. If the size of the set reaches 26, we have found every letter.

Steps

• Initialize an empty hash set.
• Iterate through each character in the sentence.
• Add the character to the set.
• After the loop, check if the size of the set is 26.

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        return len(set(sentence)) == 26

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(1) because the set will store at most 26 characters.
• Notes: Very readable and concise, especially in Python.

Boolean Array

Intuition Since the input consists only of lowercase English letters, we can use a fixed-size boolean array of length 26 to track which letters have been seen.

Steps

• Initialize a boolean array of size 26 with false values.
• Iterate through the string.
• Calculate the index for the current character (e.g., index = char - 'a').
• Mark the corresponding index in the array as true.
• Finally, check if all values in the array are true.

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        seen = [False] * 26
        for ch in sentence:
            seen[ord(ch) - ord('a')] = True
        return all(seen)

Complexity

• Time: O(n) to iterate through the string.
• Space: O(1) as the array size is constant (26).
• Notes: Slightly more verbose than a set but very efficient with low overhead.

Bit Manipulation

Intuition We can use a single 32-bit integer as a bitmask to track the presence of letters. Each bit represents a letter (e.g., bit 0 for ‘a’, bit 1 for ‘b’).

Steps

• Initialize an integer mask to 0.
• Iterate through the string.
• Calculate the bit position for the character.
• Use bitwise OR to set the corresponding bit in mask.
• After processing all characters, check if mask equals (1 << 26) - 1 (which is a binary number with the lowest 26 bits set to 1).

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        mask = 0
        for ch in sentence:
            mask |= 1 << (ord(ch) - ord('a'))
        return mask == (1 << 26) - 1

Complexity

• Time: O(n) to iterate through the string.
• Space: O(1) using only a single integer variable.
• Notes: The most space-efficient approach, utilizing bitwise operations for optimal performance.