Grokking the Coding Interview: The Original Course
Vote

0% completed

​

Solution: Pangram

Problem Statement

Solution

Code

Time Complexity

Space Complexity

Conclusion

Variants worth knowing

Problem Statement

Given a string sentence containing English letters (lower- or upper-case), return true if sentence is a Pangram, or false otherwise.

A Pangram is a sentence where every letter of the English alphabet appears at least once.

Note: The given sentence might contain other characters like digits or spaces, your solution should handle these too.

Example 1:

Input: sentence = "TheQuickBrownFoxJumpsOverTheLazyDog"
Output: true
Explanation: The sentence contains at least one occurrence of every letter of the English alphabet either in lower or upper case.

Example 2:

Input: sentence = "This is not a pangram"
Output: false
Explanation: The sentence doesn't contain at least one occurrence of every letter of the English alphabet.

Example 3:

Input: sentence = "abcdefghijklmnopqrstuvwxy1"
Output: false
Explanation: The digit is not a letter, so it does not count towards the alphabet. Only a through y are
present and z is missing, so this is not a pangram.

Constraints:

  • 1 <= sentence.length <= 1000
  • sentence consists of printable ASCII characters, which may include letters, digits and spaces.

Solution

We can use a HashSet to check if the given sentence is a pangram or not. The HashSet will be used to store all the unique characters in the sentence. The algorithm works as follows:

  1. Define seen hashSet to store all unique characters of the string.
  2. Iterate over each character of the sentence using a loop.
  3. Convert the character at index i to the lowercase letter, and store it in the currChar variable.
  4. If currChar is an alphabetical letter, add it to the seen hashSet. Characters that are not letters, such as digits and spaces, are skipped.
  5. After looping through all characters, compare the size of the HashSet with 26 (total number of alphabets). If the size of the HashSet is equal to 26, it means the sentence contains all the alphabets and is a pangram, so the function will return true. Otherwise, it will return false.

Here is the scan running on "TheQuickBrownFoxJumpsOverTheLazyDog". Move through the steps one at a time:

mediaLink

Step 1. The question is whether "TheQuickBrownFoxJumpsOverTheLazyDog" contains every letter of the alphabet. The code keeps a set of the letters it has seen. It starts empty, and the answer at the end is simply whether the set holds 26 letters.

1 of 7

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Time Complexity

  1. Iterating Over Characters: The main operation in the code is iterating over each character in the input string. If the length of the input string is n, this iteration occurs n times.

  2. Set Operations: For each character, the code performs a constant-time operation: adding the character to a HashSet if it is a letter. The time complexity for adding an element to a HashSet is typically O(1).

  3. Overall Time Complexity: Considering the iteration over n characters and constant-time set operations, the total time complexity is O(n), where n is the length of the sentence.

Space Complexity

  1. HashSet Storage: The HashSet seen is used to store the distinct characters encountered in the sentence. In the worst-case scenario, it will store all 26 letters of the alphabet.

  2. Constant Size Set: Regardless of the input sentence length, the HashSet can only grow up to a size of 26. This is because it only stores distinct English alphabet letters.

  3. Overall Space Complexity: Given the HashSet's maximum size is constant (at most 26 characters), the space complexity is O(1), meaning it is constant.

Conclusion

  • Time Complexity: O(n), where n is the length of the input string.
  • Space Complexity: O(1) (constant space, independent of input string length).

Variants worth knowing

Stop as soon as the set fills. Once seen holds 26 letters the answer cannot change, so the loop can return there instead of reading the rest of the sentence. On a long pangram whose letters all appear early, that is the difference between reading a few hundred characters and reading all of them. The complexity does not change, because a sentence that is not a pangram still has to be read to the end.

for char in sentence.lower():
    if char.isalpha():
        seen.add(char)
        if len(seen) == 26:
            return True
return False

Count into a fixed array, or a bit vector. Instead of a hash set, keep 26 slots indexed by ord(char) - ord("a"), or a single integer where bit i marks the ith letter and the answer is bits == (1 << 26) - 1. Both are still O(N) time and O(1) space, so they do not beat the set on paper. What they remove is the hashing, which makes them faster in practice and worth mentioning if an interviewer asks how you would tighten it.

Delete from a full alphabet instead of building up. Start with a set of all 26 letters, discard each character you meet, and the sentence is a pangram when the set is empty. It reads nicely and needs no isalpha check, since discarding a character that is not in the set does nothing.

T

t.kopanakis

· 17 days ago

// Using streams in Java makes it quite easy
class Solution {
  public boolean checkIfPangram(String sentence) {
    long pangram = sentence 
      .toLowerCase()
      .chars()
      .filter(ch -> ch >= 'a' && ch <= 'z')
      .distinct()
      .count();

    return pangram == 26;
  }
}
Dominik Myszkowski

Dominik Myszkowski

· 20 days ago

/*I find my solution also pretty elegant - similar but done in a different direction. First I build a Set with all the letters, then delete a letter from set whenever encountered, If the set size is zero at the end then conditions are met.*/
class Solution {
  // Function to check if given sentence is pangram
  checkIfPangram(sentence) {
    // TODO: Write your code here
    const set = new Set('abcdefghijklmnopqrstuvwxyz');
    for (const l of sentence) {
      if (set.has(l.toLowerCase())) set.delete(l.toLowerCase());
    }
    if (set.size == 0) return true;
    return false;
  }
}
Kumawat Bros

Kumawat Bros

· 2 months ago

class Solution {
  public boolean checkIfPangram(String sentence) {
    boolean seen[] = new boolean[26];
    int unique = 0;
    for(char c: sentence.toCharArray())
    {
      if(c>='A' && c<='Z')
      {
        c = (char)(c | 32);
      }
      int index = (c-'a');
      if( index >=0 && index < 26)
      {
        if(!seen[index])
        {
          seen[index] = true;
          unique++;
        }
      }   
      if(unique == 26) return true;
    }
    return unique == 26;
  }
}
Edris

Edris

· 2 months ago


class Solution {
  public boolean checkIfPangram(String sentence) {
    // TODO: Write your code here
    Set<Character> mySet = new HashSet<>();

    sentence = sentence.toLowerCase();

    for (int i = 0; i < sentence.length(); i++) {
      if (sentence.charAt(i) >= 97 && sentence.charAt(i) <= 122) {
        mySet.add(sentence.charAt(i));
      }
    }

    return mySet.size() == 26;
  }
}
Show 1 reply
7

7robertodantas

· 2 months ago

class Solution:
  def checkIfPangram(self, sentence):
    letters = set("abcdefghijklmnopqrstuvwxyz")
    for s in sentence:
      letters.discard(s.lower())
    return not letters
Show 1 reply
Nyan Htet

Nyan Htet

· 2 months ago

For JS - here's my solution using Regex to check if it's alphabetical letters:

class Solution {
  checkIfPangram(sentence) {
    const seen = new Set();

    for (let i = 0; i < sentence.length; i++){
      const lowered = sentence[i].toLowerCase();
      if (lowered.match(/[a-zA-Z]/g)){
        seen.add(lowered);
      }
    }
    return seen.size === 26
  }
}
Show 1 reply
Cole Bodine

Cole Bodine

· 4 months ago

I like this solution because it introduces a chance for the program to exit early if the solution is found before looping through the entire string unnecessarily.

class Solution:
    # Function to check if given sentence is pangram
    def checkIfPangram(self, sentence):
        seen = set()

        # Direct character loop + direct case conversion
        for char in sentence.lower():
            if char.isalpha():
                seen.add(char)

            # Early exit: Stop processing the moment we hit 26!
            if len(seen) == 26:
                return True

        # Return true if set size is 26 (total number of alphabets)
        return False
Show 1 reply
X

xha80n+9p6ne

· 5 months ago

class Solution:
  def checkIfPangram(self, sentence):
    return len({s.lower() for s in sentence if s.isalpha()}) == 26
Show 1 reply
Aziz Nosirov

Aziz Nosirov

· 6 months ago

From my understanding, the space complexity is O(1) because even though the number of letters the hash set stores can vary, it is O(1) because big O notation checks for the worst case scenario, which is 26?

Show 1 reply
Dhruv Mohindru

Dhruv Mohindru

· 7 months ago

Solution in Rust

use std::collections::HashSet;
fn check_if_pangram(input: String) -> bool {
    let mut char_set: HashSet<char> = HashSet::new();
    for c in input.chars() {
        let c = c.to_ascii_uppercase();
        if c.is_ascii() {
            char_set.insert(c);
        }
    }
    char_set.len() == 26
}
Show 1 reply

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Solution

Code

Time Complexity

Space Complexity

Conclusion

Variants worth knowing