algoadvance

Leetcode 1832. Check if the Sentence Is Pangram

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:

Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true

Input: sentence = "leetcode"
Output: false

Clarifying Questions

1. Input Constraints:
   • Can we assume that the input string contains only lowercase English letters?
   • Is there a maximum length for the input string sentence?
2. Output Specifics:
   • Should we return a boolean value?

For this problem, we assume:

• The input string sentence only contains lowercase English letters.
• The length of sentence is reasonable for standard string operations (e.g., up to 10^4 characters).

Strategy

To determine if the sentence is a pangram, we can:

1. Use a set (hash set) to track all unique letters in the sentence.
2. Iterate through each character in the sentence and add it to the set.
3. If the size of the set equals 26 (the number of letters in the English alphabet), then the sentence is a pangram; otherwise, it is not.

This approach ensures that we efficiently check for all unique letters without redundant checks.

Code

Here’s how you can implement the solution in C++:

#include <iostream>
#include <unordered_set>
#include <string>

bool checkIfPangram(const std::string& sentence) {
    // Create a set to track encountered characters
    std::unordered_set<char> characters;
    
    // Iterate over every character in the sentence
    for (char ch : sentence) {
        characters.insert(ch);  // Insert character into the set
    }
    
    // Check if we have 26 unique characters
    return characters.size() == 26;
}

// Example usage
int main() {
    std::string sentence1 = "thequickbrownfoxjumpsoverthelazydog";
    std::string sentence2 = "leetcode";
    
    std::cout << std::boolalpha; // to print boolean values as true/false
    std::cout << "Is the sentence \"" << sentence1 << "\" a pangram? " 
              << checkIfPangram(sentence1) << std::endl; // Expected output: true
    
    std::cout << "Is the sentence \"" << sentence2 << "\" a pangram? " 
              << checkIfPangram(sentence2) << std::endl; // Expected output: false
    
    return 0;
}

Time Complexity

The time complexity of this approach is O(n), where n is the length of the input sentence:

• Iterating over all characters in the sentence takes O(n) time.
• Inserting into a set and checking its size both happen in average case O(1) time per operation, thanks to the hash set implementation.

Thus, overall, this is very efficient for determining if a sentence is a pangram.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?