#2309

Easy

LeetCode Problem Workspace

Greatest English Letter in Upper and Lower Case

Find the greatest English letter that exists in both lowercase and uppercase in a string using a hash table approach.

Problem Statement

Given a string s consisting of English letters, return the greatest letter which appears in both lowercase and uppercase forms. The result must be uppercase, and return an empty string if no such letter exists.

An English letter b is considered greater than a if it comes later in the alphabet. For example, given s = "lEeTcOdE", the output should be "E" because it is the only letter appearing in both cases and no other letter is greater.

Examples

Example 1

Input: s = "lEeTcOdE"

Output: "E"

The letter 'E' is the only letter to appear in both lower and upper case.

Example 2

Input: s = "arRAzFif"

Output: "R"

The letter 'R' is the greatest letter to appear in both lower and upper case. Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.

Example 3

Input: s = "AbCdEfGhIjK"

Output: ""

There is no letter that appears in both lower and upper case.

Constraints

1 <= s.length <= 1000
s consists of lowercase and uppercase English letters.

Solution Approach

Use Two Sets for Lowercase and Uppercase

Iterate through the string, adding each lowercase letter to one set and each uppercase letter to another. Then check for letters that exist in both sets and track the maximum letter.

Check Each Letter in Reverse Alphabet Order

Loop from 'Z' to 'A' and verify if both uppercase and lowercase versions exist in the respective sets. Return the first match found as it will be the greatest letter.

Return Uppercase or Empty String

If a common letter is found, return it in uppercase. If no letter exists in both cases, return an empty string.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for scanning the string and O(1) for checking up to 26 letters. Space complexity is O(n) for storing sets of characters.

What Interviewers Usually Probe

Look for a hash table or set-based solution instead of nested loops.
Pay attention to the requirement that the result must be uppercase.
Consider iterating the alphabet in reverse to find the greatest letter efficiently.

Common Pitfalls or Variants

Common pitfalls

Returning a lowercase letter instead of the required uppercase result.
Failing to check both cases properly when letters repeat in the string.
Assuming alphabetical order from the string rather than using explicit letter comparison.

Follow-up variants

Return all letters that appear in both cases in descending order.
Find the smallest English letter present in both cases instead of the greatest.
Handle strings with non-letter characters by filtering out invalid characters before processing.

FAQ

What is the main pattern used in Greatest English Letter in Upper and Lower Case?

The problem uses a hash table plus string pattern where sets track lowercase and uppercase letters for fast lookup.

How do I return the correct letter format?

Always return the letter in uppercase regardless of how it appears in the original string.

What if no letter exists in both cases?

Return an empty string to indicate no letter satisfies the condition.

Can this solution handle long strings efficiently?

Yes, storing letters in sets ensures O(n) time complexity, even for strings up to 1000 characters.

Why iterate letters in reverse order?

Checking from 'Z' to 'A' ensures the first common letter found is the greatest, satisfying the problem requirement.

terminal

Solution

Solution 1: Hash Table + Enumeration

First, we use a hash table $ss$ to record all the letters that appear in the string $s$. Then we start enumerating from the last letter of the uppercase alphabet. If both the uppercase and lowercase forms of the current letter are in $ss$, we return that letter.

1

2

3

4

5

6

7

class Solution:
    def greatestLetter(self, s: str) -> str:
        ss = set(s)
        for c in ascii_uppercase[::-1]:
            if c in ss and c.lower() in ss:
                return c
        return ''

Solution 2: Bit Manipulation (Space Optimization)

We can use two integers $mask1$ and $mask2$ to record the lowercase and uppercase letters that appear in the string $s$, respectively. The $i$-th bit of $mask1$ indicates whether the $i$-th lowercase letter appears, and the $i$-th bit of $mask2$ indicates whether the $i$-th uppercase letter appears.

1

2

3

4

5

6

7

class Solution:
    def greatestLetter(self, s: str) -> str:
        ss = set(s)
        for c in ascii_uppercase[::-1]:
            if c in ss and c.lower() in ss:
                return c
        return ''

Continue Practicing

#2306 naming a company #2947 count beautiful substrings i #1638 count substrings that differ by one character