# Check if the Sentence Is Pangram
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-the-sentence-is-pangram)
Canonical: https://scaleengineer.com/dsa/problems/check-if-the-sentence-is-pangram
**Data structures:** Hash Table, String
**Companies:** [Vanguard](https://scaleengineer.com/companies/vanguard)
---
## Problem
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 <= 1000`
* `sentence` consists of lowercase English letters.

# Approaches
## Brute Force by Searching for Each Letter
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
- Iterate through all 26 lowercase English letters from 'a' to 'z'.
- For each letter, search the entire input `sentence` to 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`.

## Using a HashSet to Track Unique Characters
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.
**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.
**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 `HashSet` object, 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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `HashSet` is equal to 26.
- If the size is 26, return `true`; otherwise, return `false`.

## Using a Boolean Array as a Frequency Map
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.
**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.
**Pros:** Extremely efficient in both time and space.; Faster than the `HashSet` approach 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 `HashSet` if the character set were unknown or very large.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Create a boolean array, `seen`, of size 26, and initialize all its elements to `false`.
- Each index `i` in the array corresponds to the `i`-th letter of the alphabet (e.g., index 0 for 'a', 1 for 'b').
- Iterate through each character `c` of the `sentence`.
- 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 `seen` array from index 0 to 25.
- If any element `seen[i]` is `false`, it means a letter was missing, so return `false`.
- If the loop over the `seen` array completes, it means all letters were found, so return `true`.

## Optimized Approach with Bit Manipulation
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize an integer variable, `seenMask`, to 0. This integer will act as our bitmask.
- Iterate through each character `c` in the `sentence`.
- For each character, calculate its corresponding bit position: `index = c - 'a'`.
- Set the bit at this position in `seenMask` to 1. This is done using the bitwise OR operation: `seenMask |= (1 << index)`.
- After the loop, `seenMask` will 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 `seenMask` with the target pangram mask. If they are equal, return `true`; otherwise, return `false`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

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

```