Check if the Sentence Is Pangram - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You receive a lowercase sentence and need to determine whether it is a pangram—a string that contains every letter from 'a' to 'z' at least once. The task is essentially checking if all 26 English alphabet characters appear in the string.
Approach 1: Using a Set to Track Letters (O(n) time, O(1) space)
The most straightforward method uses a set (or hash set) to track unique characters encountered while iterating through the sentence. As you scan each character, insert it into the set. Since sets automatically discard duplicates, the structure eventually holds only unique letters. After processing the entire string, check whether the set size equals 26. This approach relies on constant-time hash insertions and lookups, making the scan linear with respect to the sentence length.
This technique is a classic application of a hash table for uniqueness tracking. It’s concise, readable, and widely used in interviews because it directly maps the problem requirement (unique characters) to the right data structure.
Approach 2: Boolean Array for Tracking (O(n) time, O(1) space)
A slightly more memory-efficient method replaces the set with a fixed-size boolean array of length 26. Each index corresponds to a letter: index = char - 'a'. Iterate through the sentence and mark the corresponding index as true when a character appears. After the scan, verify that every position in the array is marked true. If any entry remains false, the sentence is missing that letter.
This approach avoids hashing and uses direct indexing instead. The memory footprint is constant because the array size never exceeds 26. It also tends to run slightly faster in lower-level languages due to predictable memory access patterns. The logic is simple: iterate through the string, mark presence, then verify coverage of the alphabet.
Some implementations optimize further by maintaining a counter of discovered letters. Each time a new letter is marked for the first time, increment the counter. Once it reaches 26, you can terminate early without scanning the rest of the string.
Recommended for interviews: Both solutions run in O(n) time and O(1) space, but the boolean array approach demonstrates stronger understanding of constraints and constant-space optimization. Interviewers often expect the hash set solution first because it’s the most intuitive. Following it with the boolean array optimization shows you can reduce overhead when the input domain (26 letters) is fixed.
Approach 1: Using a Set to Track Letters
This approach leverages a set data structure to track the unique characters. The idea is to iterate through the sentence and add each letter to a set. Finally, we check if the size of the set is 26, which indicates that all letters of the alphabet are present.
This solution uses a boolean array of size 26 to represent each letter of the alphabet. As we iterate through the input sentence, we mark the respective index in the array to true. Finally, we check if all elements in the array are true to verify if the sentence is a pangram.
Complexity
Time Complexity: O(n), where n is the length of the sentence.
Space Complexity: O(1), since we use a fixed-size array of 26.
Approach 2: Boolean Array for Tracking
This method uses a boolean array of size 26 to directly map each alphabet character to an index. By iterating over each character in the sentence, we update its corresponding index in the array to true. The sentence is confirmed as a pangram if all indices in the boolean array are true.
This approach relies on a 26-element boolean array, where each index corresponds to a letter of the alphabet (0 for 'a', 1 for 'b', etc.). As we parse the sentence, each letter sets its spot to true. A final loop checks that all positions in the array are true, affirming the pangram status.
Complexity
Time Complexity: O(n), with n denoting sentence length; we check each letter.
Space Complexity: O(1), constant size boolean array.
Approach 3: Array or Hash Table
Traverse the string sentence, use an array or hash table to record the letters that have appeared, and finally check whether there are 26 letters in the array or hash table.
The time complexity is O(n), and the space complexity is O(C). Where n is the length of the string sentence, and C is the size of the character set. In this problem, C = 26.
Approach 4: Bit Manipulation
We can also use an integer mask to record the letters that have appeared, where the i-th bit of mask indicates whether the i-th letter has appeared.
Finally, check whether there are 26 1s in the binary representation of mask, that is, check whether mask is equal to 2^{26} - 1. If so, return true, otherwise return false.
The time complexity is O(n), where n is the length of the string sentence. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using a Set to Track Letters | Time Complexity: O(n), where n is the length of the sentence. |
| Boolean Array for Tracking | Time Complexity: O(n), with n denoting sentence length; we check each letter. |
| Array or Hash Table | — |
| Bit Manipulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Set to Track Letters | O(n) | O(1) | General case; simplest and most readable approach using a hash set |
| Boolean Array (26 Letters) | O(n) | O(1) | When optimizing for minimal overhead and fixed alphabet size |
Video Solution
Check if the Sentence Is Pangram | 2 Approaches | Snapdeal | Leetcode 1832 • codestorywithMIK • 23,814 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Check if the Sentence Is Pangram easy or hard?
Check if the Sentence Is Pangram Python/Java solution
How to solve Check if the Sentence Is Pangram in O(n)?
What is the best approach for Check if the Sentence Is Pangram?
Is Check if the Sentence Is Pangram asked at Google/Amazon/Meta?
What data structure is used in Check if the Sentence Is Pangram?
What is the time complexity of Check if the Sentence Is Pangram?
Ready to solve this problem?
Practice Check if the Sentence Is Pangram with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor