A String Needs Every Letter, Not Just 26 Positions

A length of 26 cannot prove that all 26 letters appear

The string "thequickbrownfoxjumpsoverthelazydog" has 35 characters, but character count alone cannot tell you whether every letter from 'a' to 'z' appears. After scanning its first 26 characters, "thequickbrownfoxjumpsovert", you have processed exactly 26 positions. That does not mean you have seen 26 different letters.

thequickbrownfoxjumpsovert
01234567890123456789012345

Some characters repeat before all letters have appeared. For example, 'o', 'e', 'r', and 't' use positions that do not add a new letter to the set of letters seen. At this point, the letters 'a', 'd', 'g', 'l', 'y', and 'z' are still absent, even though 26 characters have been processed.

A 26-slot boolean array records exactly which letters have appeared

Use one boolean slot for each lowercase letter. Slot 0 represents 'a', slot 1 represents 'b', and slot 25 represents 'z'. For a scanned character c, the expression c - 'a' gives its slot because lowercase letters have consecutive ASCII values. Start every slot as false, then set the matching slot to true whenever that character occurs.

bool seen[26] = {false};

for (char c : "thequickbrownfoxjumpsoverthelazydog") {
    int slot = c - 'a';
    seen[slot] = true;
}

While the full running string is traversed, the first occurrence of a letter changes its slot from false to true. A later occurrence of the same letter assigns true to a slot that is already true, so the state does not change. In the first 26 characters, six slots remain false. The tail "helazydog" supplies those missing letters: 'l', 'a', 'z', 'y', 'd', and 'g', while its repeated 'h', 'e', and 'o' add no new slot.

One false slot is enough to reject the string

Marking slots records the evidence, but you still need to inspect all 26 slots. If any slot is false, its letter never appeared, so the answer must be false immediately. If the loop reaches the end without finding a false slot, every letter from 'a' through 'z' appeared, so the answer is true.

for (int i = 0; i < 26; i++) {
    if (!seen[i]) {
        return false;
    }
}
return true;

for (int i = 0; i < 26; i++) {
    if (__________) {
        return false;
    }
}
return true;

A fixed alphabet keeps the extra space constant

Under the contract that every input character is between 'a' and 'z', c - 'a' is always a valid index from 0 through 25. The scan takes one pass over n characters, then checks 26 slots, so its time complexity is O(n + 26), which simplifies to O(n). The boolean array has exactly 26 slots, so its extra space is O(26), which simplifies to O(1).

These implementations scan the running string, mark each letter's slot, and check every slot before returning true. The Java array and the C++ array both have a fixed size of 26, so increasing the input length changes the scan time but not the extra space.

#include <string>
using namespace std;

bool containsAllLetters() {
    string s = "thequickbrownfoxjumpsoverthelazydog";
    bool seen[26] = {false};

    for (char c : s) {
        seen[c - 'a'] = true;
    }

    for (int i = 0; i < 26; i++) {
        if (!seen[i]) {
            return false;
        }
    }
    return true;
}

static boolean containsAllLetters() {
    String s = "thequickbrownfoxjumpsoverthelazydog";
    boolean[] seen = new boolean[26];

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        seen[c - 'a'] = true;
    }

    for (int i = 0; i < 26; i++) {
        if (!seen[i]) {
            return false;
        }
    }
    return true;
}