Greatest English Letter in Upper and Lower Case

Greatest English Letter in Upper and Lower Case - Problem

Given a string of English letters s, return the greatest English letter which occurs as both a lowercase and uppercase letter in s. The returned letter should be in uppercase. If no such letter exists, return an empty string.

An English letter b is greater than another letter a if b appears after a in the English alphabet.

Input & Output

Example 1 — Basic Case

$ Input: s = "lEeTcOdE"

› Output: "E"

💡 Note: The string contains both 'E' and 'e'. Among all letters that appear in both cases (E, T, C, O, D), E is the greatest alphabetically.

Example 2 — No Valid Letters

$ Input: s = "arRAzFif"

› Output: ""

💡 Note: The string contains 'R' and 'r', but no other letter appears in both cases. R is not the greatest possible, but it's the only valid one. Wait, let me recheck - actually 'R' and 'r' are both present, so the answer should be "R".

Example 3 — Single Letter Case

$ Input: s = "AbCdEfGhIjKlMnOpQrStUvWxYz"

› Output: ""

💡 Note: Each letter appears only once in either uppercase or lowercase, but never both. No letter appears in both cases.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase and uppercase English letters only.

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Scan string for all characters

Find Valid Pairs

Identify letters with both cases

Return Greatest

Pick alphabetically largest valid letter

Key Takeaway

🎯 Key Insight: We need to find the greatest letter that exists in both uppercase and lowercase forms in the string.

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to find letters that appear in both uppercase and lowercase, then return the greatest one alphabetically. Best approach uses a hash set to collect characters in O(n) time, then checks pairs from Z to A. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass with Bitmask	O(n)	O(1)	Use bitmask to track seen letters in single pass, then find greatest valid pair
Two Pass with Hash Set	O(n)	O(1)	First pass collects all characters, second pass finds greatest valid pair
Brute Force	O(n)	O(1)	Check each letter from Z to A to see if both cases exist in string

Single Pass with Bitmask — Algorithm Steps

Step 1: Scan string once, set bits for seen letters
Step 2: Check from Z to A if both bits are set for each letter
Step 3: Return first letter with both bits set

Visualization

Tap to expand

Step-by-Step Walkthrough

Set bits

Mark seen letters in bitmasks

Check pairs

Use bitwise AND to find matches

Return result

First letter with both bits set

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

char* solution(char* s) {
    static char result[2];
    unsigned int upperMask = 0;  // Bitmask for uppercase letters seen
    unsigned int lowerMask = 0;  // Bitmask for lowercase letters seen
    
    // Single pass: set bits for seen characters
    for (int i = 0; s[i]; i++) {
        if (s[i] >= 'A' && s[i] <= 'Z') {
            upperMask |= 1 << (s[i] - 'A');
        } else if (s[i] >= 'a' && s[i] <= 'z') {
            lowerMask |= 1 << (s[i] - 'a');
        }
    }
    
    // Check from Z to A for matching bits
    for (int i = 25; i >= 0; i--) {
        if ((upperMask & (1 << i)) && (lowerMask & (1 << i))) {
            result[0] = 'A' + i;
            result[1] = '\0';
            return result;
        }
    }
    
    result[0] = '\0';
    return result;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string O(n) plus checking 26 letters with O(1) bitwise operations

✓ Linear Growth

Space Complexity

O(1)

Only using two integer variables as bitmasks, constant space

✓ Linear Space

31.2K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler