LeetCode 1832 - Check if the Sentence Is Pangram

This problem asks us to determine whether a given string is a pangram. A pangram is a sentence that contains every lowercase English letter, from 'a' through 'z', at least once. The input is a single string named sentence.

leetcodeeasyhash-tablestring

LeetCode Problem 1832

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

This problem asks us to determine whether a given string is a pangram. A pangram is a sentence that contains every lowercase English letter, from 'a' through 'z', at least once.

The input is a single string named sentence. The problem guarantees that the string contains only lowercase English letters, which simplifies the implementation because we do not need to worry about uppercase conversion, spaces, punctuation, or special characters.

The expected output is a boolean value:

  • Return true if every English letter appears at least once.
  • Return false if even one letter is missing.

The constraints tell us that the string length is between 1 and 1000. This is a very small input size, so even relatively inefficient solutions would still run quickly. However, the goal is still to design a clean and efficient algorithm.

An important observation is that the English alphabet contains exactly 26 letters. Therefore, if the string length is less than 26, it is impossible for the sentence to be a pangram. This gives us a useful early optimization.

Several edge cases are important to consider:

  • A string shorter than 26 characters can never be a pangram.
  • A string may contain many repeated characters while missing others.
  • A string may already contain all letters before reaching the end, allowing an early return in some implementations.
  • The problem guarantees lowercase English letters only, so we do not need character normalization or filtering.

Approaches

Brute Force Approach

The brute force solution checks every letter from 'a' to 'z' individually and searches the sentence to see whether that character exists.

For example, we can iterate through all 26 letters and use a membership test such as:

if char not in sentence:

If any letter is missing, we return false. If all letters are found, we return true.

This approach is correct because it directly verifies the definition of a pangram. Every required character must appear at least once.

However, this method repeatedly scans the string. For each of the 26 letters, we may need to traverse the entire sentence. While the constraints are small enough that this still performs fine, it is less efficient than necessary.

Optimal Approach

The key insight is that we only care about whether each letter has appeared at least once. We do not care about frequency.

A hash set is perfect for this situation because sets automatically store only unique values.

We iterate through the sentence once and insert every character into a set. At the end:

  • If the set contains exactly 26 unique letters, the sentence is a pangram.
  • Otherwise, at least one letter is missing.

This works efficiently because insertion into a hash set is approximately O(1) on average.

Approach Time Complexity Space Complexity Notes
Brute Force O(26 × n), simplifies to O(n) O(1) Repeatedly scans the sentence for each alphabet letter
Optimal O(n) O(1) Uses a hash set to track unique letters

Although both simplify to linear time because 26 is constant, the hash set approach is cleaner and avoids repeated scans.

Algorithm Walkthrough

  1. First, check whether the sentence length is less than 26. If it is, immediately return false because a pangram requires all 26 letters.
  2. Create an empty hash set. This set will store every distinct character encountered in the sentence.
  3. Iterate through each character in the sentence.
  4. Insert the current character into the set. Since sets only keep unique values, duplicate letters do not increase the set size.
  5. After each insertion, optionally check whether the set size has reached 26. If it has, return true immediately because all letters have been seen.
  6. If the loop finishes and the set size is still less than 26, return false.

The hash set is chosen because it provides efficient membership and insertion operations while naturally eliminating duplicates.

Why it works

The algorithm maintains the invariant that the set contains exactly the unique letters seen so far in the sentence.

If the set size becomes 26, then every lowercase English letter must have appeared at least once, which satisfies the definition of a pangram.

If fewer than 26 unique letters exist after processing the entire sentence, then at least one alphabet letter is missing, so the sentence is not a pangram.

Python Solution

class Solution:
    def checkIfPangram(self, sentence: str) -> bool:
        if len(sentence) < 26:
            return False

        unique_letters = set()

        for char in sentence:
            unique_letters.add(char)

            if len(unique_letters) == 26:
                return True

        return False

The implementation begins with a quick length check. Since a pangram must contain all 26 letters, any shorter string can immediately return False.

Next, the solution creates a set named unique_letters. As the algorithm iterates through the sentence, each character is inserted into the set. Duplicate letters do not matter because sets automatically store only unique elements.

After each insertion, the implementation checks whether the set size has reached 26. If so, the algorithm returns True early because all alphabet letters have already appeared.

If the loop finishes without reaching 26 unique letters, the function returns False.

Go Solution

func checkIfPangram(sentence string) bool {
    if len(sentence) < 26 {
        return false
    }

    uniqueLetters := make(map[rune]bool)

    for _, char := range sentence {
        uniqueLetters[char] = true

        if len(uniqueLetters) == 26 {
            return true
        }
    }

    return false
}

The Go implementation follows the same logic as the Python version. Since Go does not have a built in set type, a map is used instead. The map keys represent unique characters, and the boolean values are simply placeholders.

The loop iterates over the string using range, which produces runes. Although the problem only contains lowercase English letters, using runes is still the idiomatic Go approach for string iteration.

No special handling for integer overflow or nil values is required because the input size is very small and the data structures are initialized explicitly.

Worked Examples

Example 1

Input:

sentence = "thequickbrownfoxjumpsoverthelazydog"

We track the set of unique letters as we iterate.

Step Character Unique Letters Count
1 t 1
2 h 2
3 e 3
4 q 4
5 u 5
... ... ...
26 z 26

Once the set reaches size 26, the algorithm immediately returns true.

Output:

true

Example 2

Input:

sentence = "leetcode"
Step Character Unique Letters
1 l {l}
2 e {l, e}
3 e {l, e}
4 t {l, e, t}
5 c {l, e, t, c}
6 o {l, e, t, c, o}
7 d {l, e, t, c, o, d}
8 e {l, e, t, c, o, d}

The final set contains only 6 unique letters, not 26.

Output:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each character is processed once
Space O(1) At most 26 lowercase letters are stored

The time complexity is linear because the algorithm traverses the sentence exactly once. Each set insertion is approximately constant time.

The space complexity is technically O(1) because the set can never store more than 26 distinct lowercase English letters, regardless of input size.

Test Cases

solution = Solution()

assert solution.checkIfPangram(
    "thequickbrownfoxjumpsoverthelazydog"
) == True  # classic pangram

assert solution.checkIfPangram(
    "leetcode"
) == False  # missing many letters

assert solution.checkIfPangram(
    "abcdefghijklmnopqrstuvwxyz"
) == True  # exact alphabet once

assert solution.checkIfPangram(
    "abcdefghijklmnopqrstuvwxy"
) == False  # missing one letter

assert solution.checkIfPangram(
    "aaaaaaaaaaaaaaaaaaaaaaaaaa"
) == False  # repeated single character

assert solution.checkIfPangram(
    "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
) == True  # alphabet repeated multiple times

assert solution.checkIfPangram(
    "qwertyuiopasdfghjklzxcvbnm"
) == True  # shuffled alphabet

assert solution.checkIfPangram(
    "abc"
) == False  # very short string

assert solution.checkIfPangram(
    "packmyboxwithfivedozenliquorjugs"
) == True  # another well known pangram
Test Why
"thequickbrownfoxjumpsoverthelazydog" Standard pangram example
"leetcode" Missing many letters
"abcdefghijklmnopqrstuvwxyz" Contains every letter exactly once
"abcdefghijklmnopqrstuvwxy" Missing one required character
"aaaaaaaaaaaaaaaaaaaaaaaaaa" Tests duplicate handling
Repeated alphabet string Ensures duplicates do not affect correctness
Shuffled alphabet Confirms order does not matter
"abc" Tests very short input
"packmyboxwithfivedozenliquorjugs" Valid pangram with natural wording

Edge Cases

One important edge case is a string shorter than 26 characters. Since there are 26 distinct lowercase English letters, it is mathematically impossible for such a string to be a pangram. Without this observation, a solution might waste time processing an input that can never succeed. The implementation handles this immediately with an early return.

Another important case is repeated characters. For example, a string containing only repeated 'a' characters could incorrectly appear valid if a solution simply counted characters rather than tracking uniqueness. Using a set guarantees that duplicate letters are stored only once, preventing this bug.

A third edge case involves strings that contain all 26 letters very early. Some implementations may continue scanning unnecessarily after already confirming the sentence is a pangram. The provided solution includes an early return once the set size reaches 26, improving efficiency while preserving correctness.