The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

A pangram is a sentence that contains every letter of the alphabet (English). There are 26 letters of the alphabet. In this context, 'a' means A, b means B, c means C. etc. In the program below, the letters A to Z are given the integer values (codes) from 0 to 25 as in the following explanation:

In the ASCII character set and corresponding coding, the whole numbers that represent A-to-Z, occur consecutively. Similarly, in the ASCII character set, whole numbers that represent a-to-z, which are different from those of A-to-Z, also occur consecutively.

In the ASCII character set, if the ASCII whole number for A is subtracted from itself, 0 will result; if the ASCII whole number for A is subtracted from the ASCII whole number for B, 1 will result; if the ASCII whole number for A is subtracted from the ASCII whole number for C, 2 will result; and so on. Similarly, if the ASCII whole number for 'a' is subtracted from itself, 0 will result; if the ASCII whole number for 'a' is subtracted from the ASCII whole number for b, 1 will result; if the ASCII whole number for 'a' is subtracted from the ASCII whole number for c, 2 will result; and so on.

In this way, both the uppercase letters and lowercase letters, will become in the range, 0-to-25, accordingly, in the program below.

One Pangram Example and One Non-pangram Example

A Pangram Example:

Here every letter of the alphabet is found, with sum repeating.

A Non-pangram Example:

    "The quick brown fox jumps over the dog."

This sentence is similar to the previous, but with the word, "lazy" not present. Here, all the letters of the alphabet are found, except for 'a', 'l', 'y' and 'z'; though some other letters still repeat.

Visited Array

A visited array is an array whose indexes are all the possible whole number values of another array, the given array (or given string). This means that the given array might have fewer or more values (elements), with some elements repeating (even more than once). On the other hand, each of the element values of the visited array, is either true or false, depending on whether its index occurs at least once, in the given array.

So, in a given array (given string) of the alphabet, whose values (codes) range from 0 to 25 (26 in total), the indexes of the visited array range from 0 to 25, ending at 25 (zero based indexing), while the values of the given array are mixed and do not really follow any order, and they may be less or more than 25. If they are more than 25, it means some of the values repeat. Any value in the given array is an index in the visited array. Any value that occurs at least once in the given array, is represented as true, in the visited array, in the element for the visited array's index that is the value in the given array. The absence of a visited array index in the given array (given string), has its value as false, in the visited array.

The visited array has a fixed size, whose indexes are all the possible whole numbers that can be a value (a character) in the given array. The given array can be shorter or same or longer than the visited array. If it is shorter, it means some indexes of the visited array are absent as values, in the given array. If it is the same, it might mean that some indexes of the visited array are absent as values in the given array and some indexes of the visited array repeat as values, in the given array; or each index in the visited array occurs only once in the given array. If it is longer, it might mean that some indexes of the visited array are absent as values in the given array, and some indexes of the visited array repeat as values, in the given array; or each index in the visited array is present at least once, in the given array, as value.

So, for the above given array (string sentence), the visited array will have all the 26 letters of the alphabet as indexes, from 0 to 25. The values of the alphabet will also appear to be from 0 to 25 in the given array (but disordered ). The length of the given array may be shorter, or same, or longer than that of the visited array. Do not forget that an uppercase letter and its corresponding lowercase letter have the same integer whole number code, for the program below.

Problem

Check if a given string is a Pangram.

Employ O(n) time and O(n+m) space.

Brute Force (naive) Approach

Strategy

Assume a set of indexes from 0 to 25 to represent any possible value in the given array. These indexes are all the different possible values of the given array, presumably. The number of these indexes is m=26.

Next iterate over all the indexes of m, and for each of these indexes, iterate over all the elements of the given array. While the iterations are going on together, check if the current index among the indexes of m is present in the given array. If any of the indexes of m is not present in the given array, return false, to mean, given string (array) is not a pangram.

This involves O(m x n) time and O(m+n) space, where m is 26 in this case, and n is the number of elements in the given string (array).

It is possible to have O(m+n) time, which is much shorter than O(m x n) time. So, the brute force approach is not addressed any further, in this tutorial.

Smart Approach

Strategy

First create an array called, visited of length 26 and all its values initialized to false. Next, iterate over the given array (given string), in one scan. For any element encountered in the given string (array), mark its corresponding index in the visited array as true (for seen or occurrence). That is, the value for the index in the visited array becomes true. If an element occurs more than once in the given array, its same index will be marked repeatedly more than once in the visited array, as true.

So the given array (string) is scanned once, while not all the elements of the visited array might be visited.

Finally, iterate over the visited array once completely (not the given array), and if any of the values of its elements is false, it means the given array (string) is not a pangram.

The Smart Program

The following program does the smart algorithm (read through the code and comments):

#include <stdio.h>
#include <stdbool.h>

const int MAX_CHAR = 26;
bool checkPangram(char s[], int n) {
    //create and initialize visited
    bool visited[MAX_CHAR];
    for (int i=0; i < MAX_CHAR; i++)
        visited[i] = false;

    for (int i = 0; i < n; i++) {
        //generate whole number codes from 0 to 25 and address visited array
        // for uppercases
        if ('A' <= s[i] && s[i] <= 'Z')
            visited[s[i] - 'A'] = true;
        // for lowercases
        else if ('a' <= s[i] && s[i] <= 'z')
            visited[s[i] - 'a'] = true;
    }

    //Look for a false in visited for non-pangram
    for (int i = 0; i < MAX_CHAR; i++) {
        if (visited[i] == false)  
            return false;
    }

    return true;
}

int main(int argc, char **argv) {
    int N1 = 0;    //length (size) of string to be determined in function below
    char stri1[] = "The quick brown fox jumps over the lazy dog.";    //given string
    
    char *ptr1 = stri1;
    while (*ptr1 != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr1++; 
        N1 += 1;
    }

    bool ret1 = checkPangram(stri1, N1);
    
    if (ret1 == true)
        printf("Given string1 is Pangram.\n");  
    else
        printf("Given string1 is Not Pangram.\n");  
        
    //second test case
    int N2 = 0;    //length (size) of string to be determined in function below
    char stri2[] = "The quick brown fox jumps over the dog.";    //given string
    
    char *ptr2 = stri2;
    while (*ptr2 != '\0') {    //in C a string ends with '\0', which should not be counted
        ptr2++; 
        N2 += 1;
    }

    bool ret2 = checkPangram(stri2, N2);
    
    if (ret2 == true)
        printf("Given string2 is Pangram.\n");  
    else
        printf("Given string2 is Not Pangram.\n");  

    return 0;
}

The output is:

    Given string1 is Pangram.
    Given string2 is Not Pangram.

The complexities are actually O(2m+2n) time and O(m+n) space, where m is the length of the visited array and n is the length of the given string. 2m time is for the creation for the visited array and its final visit to look for false. 2n time is for the determination of the length of the given input array and for its one scan iteration, in the called function.

The complexities are officially given as O(m+n) time and O(m+n) space, since coefficients (multipliers of 2 or 3 or 1/2, etc.) are normally omitted.

Thanks for reading.