Greatest English Letter in Upper and Lower Case

Greatest English Letter in Upper and Lower Case

What is this problem about?

The Greatest English Letter in Upper and Lower Case interview question asks you to find the "greatest" letter in a string that appears in both its uppercase and lowercase forms. "Greatest" refers to alphabetical order, meaning 'Z' is greater than 'A'. If no such letter exists, you should return an empty string. The input contains both uppercase and lowercase English letters.

Why is this asked in interviews?

Microsoft uses this Hash Table and String coding problem as a fast, easy screening question. It tests your ability to track character presence efficiently using Sets or boolean arrays. It also evaluates if you can iterate through character sets and perform case conversions in your chosen programming language.

Algorithmic pattern used

This problem follows a Hash Set Lookup pattern.

1. Add all characters from the input string into a Hash Set (or a boolean array of size 128) for $O(1)$ lookups.
2. Iterate through the English alphabet from 'Z' down to 'A'. This ensures that the first valid letter you find is automatically the "greatest."
3. For each uppercase letter, check if both the uppercase version AND its lowercase counterpart exist in the Set.
4. Return the first match found, or an empty string if none match.

Example explanation

String: s = "lEeTcOdE"

1. Set: {'l', 'E', 'e', 'T', 'c', 'O', 'd'} (Note: 'E' and 'e' are both present).
2. Loop from 'Z' down to 'A':
   • 'Z', 'z' in Set? No.
   • ...
   • 'E', 'e' in Set? Yes!
3. Return "E".

Common mistakes candidates make

• Iterating the String instead of Alphabet: Looping through the string and keeping track of the max character found. This requires updating a "max" variable and doing more lookups. Looping backwards through the 26 alphabet letters is much cleaner and guarantees an early exit.
• Case Conversion Errors: Not knowing how to easily convert between cases or check ascii values (char + 32 for lowercase in languages like C/C++).
• Returning Lowercase: The problem usually asks to return the uppercase letter, even if the logic finds the match.

Interview preparation tip

Whenever a string problem is limited to the English alphabet (26 characters), consider iterating over the alphabet itself rather than the string if you need to find extreme values (greatest/smallest). It bounds your search to 26 operations.