Greatest English Letter in Upper and Lower Case - Video Solutions

Problem Overview: You receive a string containing uppercase and lowercase English letters. The task is to return the greatest alphabetical letter that appears in both uppercase and lowercase forms. If no such letter exists, return an empty string. For example, if both 'A' and 'a' appear, the candidate letter is 'A', and you must return the lexicographically greatest valid one.

Approach 1: Use Two Sets to Track Upper and Lower Case Letters (O(n) time, O(1) space)

This approach scans the string and stores characters in two hash table-style sets: one for lowercase letters and one for uppercase letters. Each iteration checks the character type and inserts it into the corresponding set. After building both sets, iterate from 'Z' down to 'A'. For each letter, check whether its lowercase counterpart exists in the lowercase set. The first match is the answer because the search moves from the greatest letter downward. The alphabet size is constant (26), so the additional scan is effectively constant time.

The key insight is separating uppercase and lowercase tracking so membership checks become O(1). This method is simple, readable, and maps directly to the problem statement. Space complexity is technically O(1) because at most 26 letters are stored in each set.

Approach 2: Single Pass with Boolean Tracking Arrays (O(n) time, O(1) space)

This optimized variant replaces sets with two fixed-size boolean arrays of length 26. While iterating through the string, mark whether each lowercase or uppercase letter has been seen. For example, when encountering 'a', set lower[0] = true; when encountering 'A', set upper[0] = true. After processing the string, iterate backward from index 25 to 0 and check where both arrays contain true. The first such index corresponds to the greatest valid letter.

This approach removes hashing overhead and uses direct indexing based on ASCII offsets. Because the alphabet size is fixed, the memory footprint remains constant. The algorithm still performs a single linear pass through the string plus a constant 26-character scan. Problems involving limited character ranges often benefit from this pattern, especially in enumeration tasks.

Recommended for interviews: The boolean array approach is typically preferred because it demonstrates awareness of fixed-size constraints and efficient character indexing. The set-based approach is still perfectly valid and easier to implement quickly. Showing both indicates that you understand the straightforward solution and can optimize when the input domain allows constant-size structures.