Jobs

Interviews

Discussions

Check if the Sentence Is Pangram

Easy

Check if the Sentence Is Pangram

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input sentence case-sensitive? Should I treat uppercase and lowercase letters as distinct?
Besides English alphabet characters (a-z, A-Z), can the sentence contain other characters like numbers, punctuation, or spaces?
What should I return if the input sentence is null or empty?
Is the sentence guaranteed to be a string, or do I need to handle other data types as input?
By 'at least once', do you mean exactly once, or can a letter appear multiple times and still satisfy the pangram condition?

Brute Force Solution

Approach

We need to determine if a sentence contains every letter of the alphabet. The brute force approach will check for the presence of each letter individually, one by one, in the provided sentence.

Here's how the algorithm would work step-by-step:

Start with the first letter of the alphabet, 'a'.
Look through the entire sentence to see if the letter 'a' exists.
If 'a' isn't found, we immediately know the sentence is not a pangram, so stop.
If 'a' is found, move on to the next letter, 'b'.
Repeat the process of checking if 'b' exists in the sentence.
Continue this process for every letter of the alphabet, from 'a' to 'z'.
If we reach the end of the alphabet and have found every letter, then the sentence is a pangram.

Code Implementation

def is_pangram_brute_force(input_string):
    alphabet_string = "abcdefghijklmnopqrstuvwxyz"

    for character in alphabet_string:
        # Check each character in alphabet
        found = False

        for input_character in input_string:
            # Iterate over the input string to check presence
            if character == input_character.lower():
                found = True
                break

        # If alphabet character isn't found, it isn't a pangram
        if not found:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The outer loop iterates through each of the 26 letters of the alphabet. The inner operation involves searching for each letter within the input sentence of size 'n'. Thus, for each of the 26 letters, we perform a search that takes at most n steps. The total number of operations is then 26 * n. Since the 26 is constant, we can say that the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm iterates through the alphabet ('a' to 'z') and, for each letter, searches for its presence in the input sentence. It doesn't use any auxiliary data structures like arrays, hash maps, or sets to store intermediate results or track visited letters. The space used is limited to a few constant variables, such as the current letter being checked. Therefore, the space complexity is independent of the input sentence size N, making it O(1).

Optimal Solution

Approach

To check if a sentence is a pangram, we want to see if it contains all the letters of the alphabet. The most efficient way is to keep track of which letters we've seen and quickly determine if all 26 are present.

Here's how the algorithm would work step-by-step:

Create a simple way to remember which letters of the alphabet we've encountered in the sentence.
Go through the sentence, character by character.
For each letter, mark it as 'seen'. It doesn't matter if we've seen it before; just mark it.
After checking every letter in the sentence, quickly look to see if you've marked all 26 letters of the alphabet as 'seen'.
If all 26 letters are marked, the sentence is a pangram. Otherwise, it isn't.

Code Implementation

def is_pangram(input_string):
    alphabet_present = [False] * 26

    for char in input_string:
        if 'a' <= char <= 'z':
            # Adjust index to map 'a' to 0, 'b' to 1, etc.
            index = ord(char) - ord('a')
            alphabet_present[index] = True
        elif 'A' <= char <= 'Z':
            index = ord(char) - ord('A')
            alphabet_present[index] = True

    # Verify that each letter of the alphabet has appeared
    for present in alphabet_present:
        if not present:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input sentence of length n once to mark the presence of each letter. Marking the presence of a letter takes constant time. After the iteration, it checks if all 26 letters are present, which is a constant-time operation. Therefore, the dominant factor is the single iteration through the sentence, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm uses a fixed-size data structure to track seen letters. This data structure, representing the alphabet, has a constant size of 26, irrespective of the input sentence's length (N). Therefore, the auxiliary space used is constant, not dependent on the input size. This constant space usage is simplified to O(1).

Edge Cases

Case	How to Handle
Empty or null sentence input	Return false immediately as an empty sentence cannot be a pangram.
Sentence containing characters other than English letters (e.g., numbers, symbols, spaces)	Ignore non-letter characters during alphabet presence check, focusing only on 'a'-'z' or 'A'-'Z'.
Sentence containing only uppercase letters	Convert all letters to lowercase before checking for alphabet completeness to ensure case-insensitivity.
Sentence containing only lowercase letters	Process directly after potential conversion to lowercase as part of general algorithm.
Sentence is very long (large input size)	Use a boolean array or set to track the presence of each alphabet letter, ensuring efficient O(n) time complexity despite large input.
Sentence containing duplicate letters, with some letters missing	The set or boolean array ensures duplicates do not falsely indicate completeness, correctly identifying the missing letters.
Sentence consisting of only spaces or other non-alphabetic characters	After stripping or ignoring non-alphabetic characters, the sentence should be treated like an empty string.
Sentence containing Unicode characters outside the basic English alphabet	Filter out Unicode characters that are not within the English alphabet range before the alphabet check.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input sentence case-sensitive? Should I treat uppercase and lowercase letters as distinct?
Besides English alphabet characters (a-z, A-Z), can the sentence contain other characters like numbers, punctuation, or spaces?
What should I return if the input sentence is null or empty?
Is the sentence guaranteed to be a string, or do I need to handle other data types as input?
By 'at least once', do you mean exactly once, or can a letter appear multiple times and still satisfy the pangram condition?

Brute Force Solution

Approach

We need to determine if a sentence contains every letter of the alphabet. The brute force approach will check for the presence of each letter individually, one by one, in the provided sentence.

Here's how the algorithm would work step-by-step:

Start with the first letter of the alphabet, 'a'.
Look through the entire sentence to see if the letter 'a' exists.
If 'a' isn't found, we immediately know the sentence is not a pangram, so stop.
If 'a' is found, move on to the next letter, 'b'.
Repeat the process of checking if 'b' exists in the sentence.
Continue this process for every letter of the alphabet, from 'a' to 'z'.
If we reach the end of the alphabet and have found every letter, then the sentence is a pangram.

Code Implementation

def is_pangram_brute_force(input_string):
    alphabet_string = "abcdefghijklmnopqrstuvwxyz"

    for character in alphabet_string:
        # Check each character in alphabet
        found = False

        for input_character in input_string:
            # Iterate over the input string to check presence
            if character == input_character.lower():
                found = True
                break

        # If alphabet character isn't found, it isn't a pangram
        if not found:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create a simple way to remember which letters of the alphabet we've encountered in the sentence.
Go through the sentence, character by character.
For each letter, mark it as 'seen'. It doesn't matter if we've seen it before; just mark it.
After checking every letter in the sentence, quickly look to see if you've marked all 26 letters of the alphabet as 'seen'.
If all 26 letters are marked, the sentence is a pangram. Otherwise, it isn't.

Code Implementation

def is_pangram(input_string):
    alphabet_present = [False] * 26

    for char in input_string:
        if 'a' <= char <= 'z':
            # Adjust index to map 'a' to 0, 'b' to 1, etc.
            index = ord(char) - ord('a')
            alphabet_present[index] = True
        elif 'A' <= char <= 'Z':
            index = ord(char) - ord('A')
            alphabet_present[index] = True

    # Verify that each letter of the alphabet has appeared
    for present in alphabet_present:
        if not present:
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null sentence input	Return false immediately as an empty sentence cannot be a pangram.
Sentence containing characters other than English letters (e.g., numbers, symbols, spaces)	Ignore non-letter characters during alphabet presence check, focusing only on 'a'-'z' or 'A'-'Z'.
Sentence containing only uppercase letters	Convert all letters to lowercase before checking for alphabet completeness to ensure case-insensitivity.
Sentence containing only lowercase letters	Process directly after potential conversion to lowercase as part of general algorithm.
Sentence is very long (large input size)	Use a boolean array or set to track the presence of each alphabet letter, ensuring efficient O(n) time complexity despite large input.
Sentence containing duplicate letters, with some letters missing	The set or boolean array ensures duplicates do not falsely indicate completeness, correctly identifying the missing letters.
Sentence consisting of only spaces or other non-alphabetic characters	After stripping or ignoring non-alphabetic characters, the sentence should be treated like an empty string.
Sentence containing Unicode characters outside the basic English alphabet	Filter out Unicode characters that are not within the English alphabet range before the alphabet check.