Get missing letters - TopCoder challenge

I'm working on a TopCoder problem which seeks to find the letters preventing an input sentence from being a pangram in all caps, alphabetical order.

MissingLetters.h

#ifndef _MISSING_LETTERS_H_
#define _MISSING_LETTERS_H_

#include 
#include 
#include 

class MissingLetters {
  public:
    MissingLetters() {}
    std::string getMissingLetters(std::string sentence);    
};

// Find the difference between two sets, set(lowercase(sentence)) & set([a-z])

std::string MissingLetters::getMissingLetters(std::string sentence) {
   std::set sentence_set;
   std::string missing_letters = "";

   // Put each letter in the sentence into a set, O(n log n)
   for(size_t i = 0; i < sentence.size(); ++i) {
      sentence_set.insert(toupper(sentence[i]));      
   }

   // For each letter [A-Z], add letters that aren't in the set, O(1)
   for(char letter='A'; letter <= 'Z'; ++letter) {

      if(sentence_set.find(letter) == sentence_set.end()) {
         missing_letters+=letter;      
      }
   }

   return missing_letters;
}

#endif // _MISSING_LETTERS_H_

I'd like this to be as fast as possible. My method, getMissingLetters is currently \$O(n \log{n})\$ running-time, where \$n\$ is the length of the the sentence.

Any other implementations, including different data structures, would be great if they're faster.

Any tips?

Since the size of the alphabet is fixed, you don't need a set, a boolean array will be enough:

• Initialize a boolean array, with size of the alphabet, all values false

• For each letter in the input string, set the flag to true for index letter - 'A'

• After the entire input string is processed, iterate over the boolean array, if the value is false for an index, then append the character index + 'A' to the list of missing letters

The time complexity of this alternative algorithm is \$O(n)\$ where \$n\$ is the size of the input string, space complexity is \$O(1)\$, for the size of the alphabet.

StackExchange Code Review Q#104977, answer score: 4