1832. Check if the Sentence Is Pangram

Hello, reader 👋🏽 ! Welcome to day 17 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1832. Check if the Sentence Is Pangram.

🤔 Problem Statement

• A pangram is a sentence where every alphabet of the English language appears at least once.
• Given a sentence, return true if it is a pangram, else false.
• E.g.:
  • Input: sentence = "thequickbrownfoxjumpsoverthelazydog" => Output: true
  • Input: sentence = "leetcode" =>Output: false`

💬 Thought Process - Count Array

• Since we have to check the occurrence of every character, we can use an array to keep the count of the occurrence of every character from letters a to z.
• If a character is present in the string, we increment the count, else they remain 0.
• Hence, we can use a count array to check after processing the sentence if for any character index. If the count for any character is 0, then it's not present in the sentence.

• Since internally ASCII values are used for characters and we need to convert them from index 0 to 25, we will have to do the following: ch - 'a', where ch: current character.

  • We will keep subtracting 'a' from any character we see, to convert to 0-based indices.
  • The ASCII value for z is 122 and a is 97. When we subtract a from z, it basically means: 122-98 = 25.

• Let's look at the code now:

👩🏽‍💻 Solution - Count Array

• Below is the code for the approach to maintain a count/ boolean array.

  class Solution {
    public boolean checkIfPangram(String sentence) {
        if(sentence == null || sentence.length() == 0) {
            return false;
        }
  
        int[] count = new int[26];
        int n = sentence.length();
  
        for(int i = 0; i<n; i++) {
            char ch = sentence.charAt(i);
            count[ch-'a']++;
        }
  
        for(int c: count) {
            if(c == 0) {
                return false;
            }
        }
  
        return true;
    }
  }
  

  Time Complexity: O(n)
  - n = number of characters in sentence.
  - since we are iterating through every char in the sentence once.
  Space Complexity: O(1)
  - since we are using an array of fixed size to keep track of occurrences.
  

💬 Thought Process - Boolean array/ Set

• Since we necessarily don't care about the occurrences of characters, we can simply add a marker if the character is present.
• Say a boolean array or a set to keep track of characters seen so far.
• If we use a boolean array, then:
  • we mark any occurrence of character as true, else they remain false.
  • And after processing, we can traverse through every index to check if any value is false.

• If we use a set, then:

  • we can add characters to the set once they are present in the string.
  • And after processing, since the set only stores unique values, if the size is not 26, then we can confirm that there are missing characters.

• Let's code this out now. I will be using a set here.

👩🏽‍💻 Solution - Boolean array/ Set

• Below is the code for the approach to maintain a set to mark occurrences of a character.

  class Solution {
    public boolean checkIfPangram(String sentence) {
        if(sentence == null || sentence.length() == 0) {
            return false;
        }
  
        int n = sentence.length();
        Set<Character> set = new HashSet();
  
        for(int i = 0; i<n; i++) {
            char ch = sentence.charAt(i);
            set.add(ch);
        }
  
        return set.size() == 26;
    }
  }
  

  Time Complexity: O(n)
  - n = number of characters in sentence.
  - since we are iterating through every char in the sentence once.
  Space Complexity: O(1)
  - since we are using an array of fixed size to keep track of occurrences.
  

💬 Thought Process - Bit masking

• In the above two approaches, we are marking every occurrence of the character separately.
• Instead, we can use a single value that can represent the occurrences of all characters in the string.
• We can create a bit mask such that, if a mask at any bit is 1, it represents presence of character and 0 otherwise.
• Hence we need to convert characters in terms of bits such that the LSB represents a and the MSB represents B.

• Something like shown below:

  • 1 => represents presence of a
  • 10 => represents presence of b
  • 100 => represents presence of c
    ... so on and finally
  • 10000000000000000000000000 => represents presence of z

• To do this, we would need to represent ASCII values in terms of indices from 0. As discussed above, this can be done by subtracting a from any character.

• Once we get the value ch - 'a', we have to left shift 1 by that many times.
• So if it's a, we left shift 1 by 0 times. If b, we left shift 1 by 1 time,.. and so on until z where we left shift 1 25 times.
• Then we need to combine all these representations of multiple characters into a single mask. We can do that using the bitwise or |.
• Hence, to represent string ab, we do => 1 || 10 => 11.
• And finally, to check if all characters appear, we use the mask: 11111111111111111111111111. Because this represents all the 26 characters present in the sentence.

• And if our mask that represents occurrence of every character equals this mask, then we return true, otherwise false.

• Now let's code the exact same thing out.

👩🏽‍💻 Solution - Bit masking

• Below is the code for the approach to maintain a bit mask to represent occurrences of characters.

  class Solution {
      public boolean checkIfPangram(String sentence) {
          if(sentence == null || sentence.length() == 0) {
              return false;
          }
  
          int mask = 0;
          int n = sentence.length();
          for(int i = 0; i<n; i++) {
              char ch = sentence.charAt(i);
  
              int maskNumber = ch-'a';
              mask |= 1 << maskNumber;
          }
          int test = (1<<26) - 1;
          return (mask & test) == test;
      }
  }
  

  Time Complexity: O(n)
    - n = number of characters in sentence.
    - since we are iterating through every char in the sentence once.
  Space Complexity: O(1)
    - since we are using an array of fixed size to keep track of occurrences.
  

You can find the code for this problem on GitHub repo: 1832. Check if the Sentence Is Pangram.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!