Check if the Sentence Is Pangram
EasyPrompt
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.
Example 1:
Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true
Explanation: sentence contains at least one of every letter of the English alphabet.Example 2:
Input: sentence = "leetcode"
Output: false
Constraints:
1 <= sentence.length <= 1000sentenceconsists of lowercase English letters.
Approaches
4 approaches with complexity analysis and trade-offs.
This straightforward approach checks the condition for a pangram directly. It verifies the presence of every single letter of the alphabet, one by one, by searching for it within the given sentence. If it finds that even one letter is missing, it stops and returns false. Only if all 26 letters are found does it confirm the sentence is a pangram.
Algorithm
- Iterate through all 26 lowercase English letters from 'a' to 'z'.
- For each letter, search the entire input
sentenceto check for its presence. - A common way to search is using
sentence.indexOf(char)which returns -1 if the character is not found. - If any character is not found in the sentence, we can immediately conclude it's not a pangram and return
false. - If the loop completes without finding any missing character, it means all 26 letters are present, and we return
true.
Walkthrough
The core idea is to verify the presence of all 26 required characters one by one.
We loop from 'a' to 'z'. In each iteration, we take one letter and scan the entire input sentence to find it. Java's String.indexOf() method is well-suited for this search; it returns the index of the first occurrence of a character or -1 if the character is not present.
If at any point indexOf() returns -1, we know a letter from the alphabet is not in the sentence. We can then conclude that the sentence is not a pangram and return false immediately, without checking the remaining letters.
If the loop completes successfully without returning false, it implies that every letter from 'a' to 'z' was found in the sentence, making it a pangram. We then return true.
class Solution { public boolean checkIfPangram(String sentence) { // Iterate through all 26 lowercase letters. for (char c = 'a'; c <= 'z'; c++) { // Check if the sentence contains the current character. // indexOf returns -1 if the character is not found. if (sentence.indexOf(c) == -1) { // If any character is missing, it's not a pangram. return false; } } // If the loop completes, all characters were found. return true; }}Complexity
Time
O(N). Although the asymptotic complexity is linear, it's practically O(26 * N), where N is the length of the sentence. The outer loop runs a constant 26 times, and inside, `indexOf()` can take up to O(N) time. This makes it slower than single-pass approaches.
Space
O(1), as no additional space that scales with the input size is allocated.
Trade-offs
Pros
The logic is very simple and easy to understand.
It uses O(1) extra space.
Cons
This approach is inefficient because it repeatedly scans the input string. For a sentence of length N, it performs up to 26 full scans, leading to a high constant factor in its time complexity.
It does not take advantage of more efficient data structures for presence checking.
A more efficient method is to use a HashSet to keep track of the unique letters we have seen. We can iterate through the sentence just once, adding each character to the set. Since a set only stores unique elements, we can simply check the size of the set at the end. If the size is 26, we know every letter of the alphabet was present.
Algorithm
- Initialize an empty
HashSet<Character>. - Iterate through each character of the input
sentence. - For each character, add it to the
HashSet. The set will automatically handle duplicates. - After the loop finishes, the set will contain all the unique characters from the sentence.
- Check if the size of the
HashSetis equal to 26. - If the size is 26, return
true; otherwise, returnfalse.
Walkthrough
This approach leverages a HashSet, a data structure that stores only unique elements and provides, on average, O(1) time complexity for adding and checking for the existence of an element.
We iterate through the input sentence just once. For each character in the sentence, we add it to the HashSet. The set's internal logic ensures that if we try to add a character that's already present, the set remains unchanged.
After this single pass, the HashSet contains a complete collection of all the unique letters found in the sentence. A sentence is a pangram if and only if it contains all 26 unique lowercase English letters. Therefore, the problem reduces to checking if the final size of our HashSet is 26.
import java.util.HashSet;import java.util.Set; class Solution { public boolean checkIfPangram(String sentence) { // Create a HashSet to store the unique characters. Set<Character> seenLetters = new HashSet<>(); // Iterate over the sentence and add each character to the set. for (char c : sentence.toCharArray()) { seenLetters.add(c); } // A pangram must contain all 26 unique letters. return seenLetters.size() == 26; }}Complexity
Time
O(N), where N is the length of the sentence. We iterate through the string once, and each `add` operation into the `HashSet` takes O(1) time on average.
Space
O(1). The `HashSet` will store at most 26 unique characters, corresponding to the letters of the alphabet. Therefore, the space required is constant and does not depend on the length of the input sentence.
Trade-offs
Pros
Efficient time complexity with a single pass over the input string.
Code is clean, concise, and easy to reason about.
Cons
Incurs a slight overhead from using a
HashSetobject, including memory for the hash table structure and the cost of computing hash codes for characters.Can be slightly slower than a direct array-based approach due to this overhead.
This approach improves upon the HashSet by using a simple boolean array as a direct address table. Since we know the character set is limited to 26 lowercase English letters, we can use an array of size 26 to mark the presence of each letter. This avoids the overhead of hashing and object creation, making it very efficient.
Algorithm
- Create a boolean array,
seen, of size 26, and initialize all its elements tofalse. - Each index
iin the array corresponds to thei-th letter of the alphabet (e.g., index 0 for 'a', 1 for 'b'). - Iterate through each character
cof thesentence. - For each character, calculate its corresponding index:
index = c - 'a'. - Mark the letter as seen by setting
seen[index] = true. - After iterating through the entire sentence, loop through the
seenarray from index 0 to 25. - If any element
seen[i]isfalse, it means a letter was missing, so returnfalse. - If the loop over the
seenarray completes, it means all letters were found, so returntrue.
Walkthrough
Instead of a HashSet, we can use a simple boolean array of size 26, which acts as a frequency map. Each index in the array corresponds to a letter of the alphabet: index 0 for 'a', 1 for 'b', and so on. A value of true at an index indicates the corresponding letter has been seen.
We initialize the seen array with all false values. Then, we make a single pass through the input sentence. For each character c, we calculate its alphabetical index (index = c - 'a') and set seen[index] to true.
After processing the whole sentence, we check our seen array. If all 26 entries are true, the sentence is a pangram. A simple loop through the seen array can verify this. If we find any false value, we return false.
An optimization is to also keep a count of unique characters seen. When we see a character for the first time, we increment the counter. The sentence is a pangram if the final count is 26.
class Solution { public boolean checkIfPangram(String sentence) { // A boolean array to mark found letters. boolean[] seen = new boolean[26]; // Iterate through the sentence. for (char c : sentence.toCharArray()) { // Mark the corresponding letter as seen. // 'c' - 'a' gives an index from 0 to 25. seen[c - 'a'] = true; } // Check if all letters have been seen. for (boolean letterSeen : seen) { if (!letterSeen) { // If any letter was not seen, it's not a pangram. return false; } } // All letters were seen. return true; }}Complexity
Time
O(N), where N is the length of the sentence. We perform a single pass through the string (O(N)) and then a single pass through our 26-element array (O(26)). The total time is O(N + 26), which simplifies to O(N).
Space
O(1). We use a boolean array of a fixed size (26), which is constant space.
Trade-offs
Pros
Extremely efficient in both time and space.
Faster than the
HashSetapproach due to direct array indexing and no object/hashing overhead.The logic is still quite straightforward.
Cons
This approach is specifically tailored to a fixed, small alphabet. It's less generic than a
HashSetif the character set were unknown or very large.
This is a highly optimized approach that uses a single integer as a bitmask to track which letters have been seen. Each of the first 26 bits of the integer corresponds to a letter of the alphabet. By using fast, low-level bitwise operations, this method achieves excellent performance with minimal memory usage.
Algorithm
- Initialize an integer variable,
seenMask, to 0. This integer will act as our bitmask. - Iterate through each character
cin thesentence. - For each character, calculate its corresponding bit position:
index = c - 'a'. - Set the bit at this position in
seenMaskto 1. This is done using the bitwise OR operation:seenMask |= (1 << index). - After the loop,
seenMaskwill have a '1' at each bit position corresponding to a letter present in the sentence. - The target mask for a pangram (all 26 letters present) is an integer with its first 26 bits set to 1. This value is
(1 << 26) - 1. - Compare
seenMaskwith the target pangram mask. If they are equal, returntrue; otherwise, returnfalse.
Walkthrough
This solution is a clever optimization of the boolean array approach. Since we only need to store 26 true/false values, we can use the bits of a single integer variable. An int in Java has 32 bits, which is sufficient.
The 0th bit can represent 'a', the 1st bit 'b', and so on, up to the 25th bit for 'z'. We start with an integer seenMask initialized to 0 (all bits are 0).
We iterate through the sentence. For each character c, we determine its corresponding bit index (index = c - 'a'). We then need to set the index-th bit of seenMask to 1. The expression 1 << index creates a number that has only the index-th bit set. Using a bitwise OR (|=) with our seenMask sets that bit to 1 without affecting the other bits.
After the loop, we check if seenMask represents a full set of 26 letters. The integer value for a pangram would have its first 26 bits all set to 1. This number is 111...1 (26 times) in binary, which is equal to (2^26) - 1, or (1 << 26) - 1 in code. If our seenMask equals this value, the sentence is a pangram.
class Solution { public boolean checkIfPangram(String sentence) { // An integer can be used as a bitmask for 26 letters. int seenMask = 0; for (char c : sentence.toCharArray()) { int index = c - 'a'; // Create a bitmask for the current character. int bit = 1 << index; // Use bitwise OR to set the bit in our seenMask. seenMask |= bit; } // The target mask for a pangram has the first 26 bits set to 1. // This is equivalent to (2^26) - 1. int pangramMask = (1 << 26) - 1; return seenMask == pangramMask; }}Complexity
Time
O(N), where N is the length of the sentence. We iterate through the string once, and all bitwise operations are constant time.
Space
O(1). Only a single integer variable is used, regardless of the input size.
Trade-offs
Pros
The most memory-efficient solution, using only a single integer for tracking.
Extremely fast due to the use of bitwise operations, which are often executed in a single CPU cycle.
Cons
The logic can be less intuitive for developers not comfortable with bitwise operations.
Like the array approach, it's tailored to a small, fixed-size alphabet.
Solutions
Solution
class Solution {public boolean checkIfPangram(String sentence) { boolean[] vis = new boolean[26]; for (int i = 0; i < sentence.length(); ++i) { vis[sentence.charAt(i) - 'a'] = true; } for (boolean v : vis) { if (!v) { return false; } } return true; }}class Solution {public: bool checkIfPangram(string sentence) { int vis[26] = {0}; for (char &c : sentence) vis[c - 'a'] = 1; for (int &v : vis) if (!v) return false; return true; }};class Solution: def checkIfPangram( self, sentence: str) -> bool: return len(set(sentence)) == 26Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.