Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Pangram

Problem Statement

Solution

Code

Time Complexity

Space Complexity

Conclusion

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.

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 alphabetical letter, add it in the seen hashSet.
  5. Add each character to the HashSet.
  6. 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.
Image

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's 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).
Nyan Htet

Nyan Htet

· 3 days 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
  }
}
Cole Bodine

Cole Bodine

· a month 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
X

xha80n+9p6ne

· 3 months ago

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

Aziz Nosirov

· 3 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?

Dhruv Mohindru

Dhruv Mohindru

· 5 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
}
N

naveendranambula

· 5 months ago

bool checkIfPangram(string sentence) {
        vector<int> numbers(26, 0);

        for (int i = 0; i < sentence.length(); i++) {
            if (sentence[i] >= 'a' && sentence[i] <= 'z') {
                numbers[sentence[i] - 'a']++;
            } else if (sentence[i] >= 'A' && sentence[i] <= 'Z') {
                numbers[sentence[i] - 'A']++;
            }
        }

        for (auto i : numbers) {
            if (i == 0) {
                return false;
            }
        }

        return true;
    }

A simple counting sort should be the best approach here, without any Set or Map to eliminate the unnecessary indexing,

Nabeel Keblawi

Nabeel Keblawi

· 2 years ago

What I did was first convert the sentence to lower case, then declared an alphabet string to loop through it and search for each character in the sentence.

Since we're looking for pangrams that have ALL the letters in the alphabet, if the "char not in sentence_lower" is ever found true, then abort the function by returning False. If the loop completes without executing the conditional block, then return True.

More than one way to skin a cat...

class Solution:
  def checkIfPangram(self, sentence):
    sentence_lower = sentence.lower()
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    for char in alphabet:
      if char not in sentence_lower:
        return False
    return True
Show 3 replies
Akmal Alikhujaev

Akmal Alikhujaev

· 2 years ago

Since there are only 26 letters in English alphabet we can use a bit vector (bit vector is a single 32-bit integer) to map every character to a single bit index like this:

'a' -> 0th bit

'b' -> 1st bit

...

'z' -> 25th bit

While iterating through the string, if the current character is letter, we have to lowercase it (if required) and then we can get its bitIndex by subtracting lowercase 'a' from the character. So we get the following mapping:

'a' - 'a' -> 0

'b' - 'a' -> 1

'c' - 'a' -> 2

....

'z' - 'a' -> 25

That gives us the bit index, which we need to set to 1 (marking the character as present). We can set a particular bit on an integer x using following operation

x = x | (1 << bitIndex);

If you don't know the expression above, I highly suggest to read about b

Jonathan Cook

Jonathan Cook

· 2 years ago

I wrote a solution in C# that uses arrays and could also return the specifics on which letters were upper and lower case

A

Alex

· 3 years ago

The Java solution has a space complexity of O(N), not O(1), because toCharArray() allocates a new array: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/String.html#toCharArray()

A solution using charAt() would have O(1) space complexity.

Reading Progress

0%

On This Page

Problem Statement

Solution

Code

Time Complexity

Space Complexity

Conclusion