Code Implementation

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

class Solution {
public:
    bool checkIfPangram(string sentence) {
        vector<bool> seen(26, false);
        for (char c : sentence) {
            seen[c - 'a'] = true;
        }
        for (bool b : seen) {
            if (!b) return false;
        }
        return true;
    }
};
      

class Solution {
    public boolean checkIfPangram(String sentence) {
        boolean[] seen = new boolean[26];
        for (char c : sentence.toCharArray()) {
            seen[c - 'a'] = true;
        }
        for (boolean b : seen) {
            if (!b) return false;
        }
        return true;
    }
}
      

var checkIfPangram = function(sentence) {
    const seen = new Array(26).fill(false);
    for (let c of sentence) {
        seen[c.charCodeAt(0) - 'a'.charCodeAt(0)] = true;
    }
    for (let b of seen) {
        if (!b) return false;
    }
    return true;
};
      

Problem Description

You are given a string sentence that consists of only lowercase English letters. Your task is to determine if sentence is a pangram. A pangram is a sentence that contains every letter of the English alphabet at least once.

• Return true if sentence is a pangram, otherwise return false.
• The length of sentence can be up to 1000 characters.
• Each letter from 'a' to 'z' must appear at least once.

Thought Process

The problem asks if a given sentence contains every letter from 'a' to 'z' at least once. At first, one might think of checking for every letter by looping through the alphabet and verifying its presence in the string. However, this would be inefficient for long strings.

Instead, we can optimize by tracking which letters we have seen as we iterate through the string. If we have seen all 26 letters, we can immediately return true. If we reach the end and some letters are missing, we return false.

This approach avoids unnecessary repeated searches and leverages efficient data structures to keep track of the letters.

Solution Approach

Here’s a step-by-step explanation of the efficient solution:

1. Tracking Letters: We need a way to remember which letters we have already seen. This can be done using:
   • A set (in Python/JavaScript) or
   • An array of 26 booleans (in Java/C++), each representing one letter of the alphabet.
2. Iterate Through the Sentence: For each character in sentence, mark the corresponding letter as seen.
3. Check for All Letters: After processing the string, check if all 26 letters have been seen. If so, the sentence is a pangram.
4. Early Exit (Optional): If at any point all letters have been seen, you can return true immediately for further optimization.

This method is efficient because each letter is processed only once, and lookups and updates to our tracking structure are constant time operations.

Example Walkthrough

Let's consider the input sentence = "thequickbrownfoxjumpsoverthelazydog".

1. We start with an empty set (or boolean array) to track seen letters.
2. As we iterate through each character, we add it to our set (or mark its position in the array).
3. After processing the entire sentence, our set will contain all 26 letters (or all values in the array will be true).
4. Since every letter from 'a' to 'z' has appeared at least once, we return true.

If the sentence were "leetcode", after processing, not all letters would be present. We would return false.

Time and Space Complexity

• Brute-force Approach:
  • For each letter in the alphabet, check if it exists in the sentence. This is O(26 * N), where N is the length of the sentence.
• Optimized Approach:
  • Iterate through the string once: O(N).
  • Tracking letters in a set or boolean array is O(1) per operation.
  • Checking if all letters are present is O(1) (since the alphabet size is fixed at 26).
  • Space Complexity: O(1) extra space, since the set or array size is fixed and does not depend on input length.

Summary

To determine if a sentence is a pangram, we efficiently track the presence of each letter using a set or boolean array. By iterating through the sentence once, we ensure each letter is counted, and we can quickly check if all 26 letters are present. This approach is both time and space efficient, leveraging the fixed size of the English alphabet for a clean and elegant solution.