Problem Description

You are given a string s containing English letters. Your task is to find the greatest English letter that appears in the string as both a lowercase and uppercase letter.

The problem asks you to:

• Check which letters appear in both lowercase and uppercase forms in the string
• Among these letters, find the greatest one (the one that appears latest in the alphabet)
• Return this letter in uppercase format
• If no letter exists in both forms, return an empty string ""

For example:

• If s = "arRAzFif", the letter 'r' appears as both 'r' and 'R', and the letter 'f' appears as both 'f' and 'F'. Since 'R' comes after 'F' in the alphabet, the answer is "R".
• If s = "AbCdEfGhIjK", no letter appears in both lowercase and uppercase forms, so the answer is "".

The solution uses a hash table to store all characters from the string, then iterates through the uppercase letters from 'Z' to 'A' (in reverse order to find the greatest first). For each uppercase letter, it checks if both the uppercase and lowercase versions exist in the hash table. The first match found is returned as it will be the greatest letter that satisfies the condition.

Intuition

The key insight is that we need to find letters that appear in both cases and then select the greatest one. To check if a letter exists in both forms, we need to verify that both 'X' and 'x' are present in the string for some letter X.

The straightforward approach would be to check every character in the string, but this would require us to keep track of which letters we've seen in both forms and then find the maximum among them.

A more elegant approach is to work backwards from the greatest possible letter. Since we want the greatest letter that appears in both forms, why not start checking from 'Z'? This way, the first letter we find that satisfies our condition will automatically be the greatest one - we can return it immediately without comparing with other candidates.

To efficiently check if a character exists in the string, we can use a hash table (set) to store all characters from the string. This gives us O(1) lookup time for checking whether a specific character exists.

The algorithm becomes:

1. Store all characters from the string in a set for quick lookup
2. Iterate through the uppercase letters from 'Z' to 'A' (reverse alphabetical order)
3. For each uppercase letter, check if both it and its lowercase version exist in the set
4. Return the first match we find (which will be the greatest due to our iteration order)
5. If no match is found after checking all letters, return an empty string

This approach is efficient with O(n) time to build the set and O(26) for checking the letters, resulting in O(n) overall time complexity.

Solution Approach

The solution uses a hash table (implemented as a Python set) combined with reverse enumeration through uppercase letters.

Step 1: Create a Hash Table

ss = set(s)

We convert the input string s into a set ss. This allows us to check if any character exists in the string with O(1) time complexity. The set automatically handles duplicates and stores each unique character only once.

Step 2: Enumerate Uppercase Letters in Reverse

for c in ascii_uppercase[::-1]:

We iterate through the uppercase letters from 'Z' to 'A' using ascii_uppercase[::-1]. The [::-1] reverses the string of uppercase letters, so we check them in descending order. This ensures we find the greatest letter first.

Step 3: Check Both Cases

if c in ss and c.lower() in ss:
    return c

For each uppercase letter c, we check two conditions:

• c in ss: Checks if the uppercase version exists in the original string
• c.lower() in ss: Checks if the lowercase version exists in the original string

If both conditions are true, we immediately return c (in uppercase). Since we're iterating from 'Z' to 'A', the first match we find is guaranteed to be the greatest letter.

Step 4: Return Empty String if No Match

return ''

If the loop completes without finding any letter that appears in both cases, we return an empty string.

Time Complexity: O(n) where n is the length of the input string (for creating the set). The iteration through 26 letters is O(1) constant time.

Space Complexity: O(n) in the worst case for storing the set of characters.

Example Walkthrough

Let's walk through the solution with the example s = "arRAzFif".

Step 1: Create the hash table (set) We convert the string into a set to store all unique characters:

• Input string: "arRAzFif"
• Set ss = {'a', 'r', 'R', 'A', 'z', 'F', 'i', 'f'}

Step 2: Check uppercase letters from Z to A We iterate through uppercase letters in reverse order:

• Check 'Z':

  • Is 'Z' in ss? No ❌
  • Skip to next letter

• Check 'Y':

  • Is 'Y' in ss? No ❌
  • Skip to next letter

• ... (continue checking X, W, V, U, T, S) ...

• Check 'R':

  • Is 'R' in ss? Yes ✓ (we have 'R')
  • Is 'r' in ss? Yes ✓ (we have 'r')
  • Both conditions satisfied! Return "R"

We found our answer without needing to check further letters. Even though 'F' and 'f' also both exist in the string, we don't need to check them because 'R' comes later in the alphabet and we found it first by iterating backwards.

Result: "R"

This demonstrates why iterating from Z to A is efficient - the first match we find is automatically the greatest letter that appears in both cases.

Solution Implementation

Time and Space Complexity

The time complexity is O(n + C), where n is the length of the string s and C is the size of the character set (26 for uppercase letters). Creating the set from string s takes O(n) time. The loop iterates through all uppercase letters in reverse order, which is O(C) iterations. Each iteration performs two constant-time set lookups (c in ss and c.lower() in ss), resulting in O(1) per iteration. Therefore, the total time complexity is O(n) + O(C) = O(n + C), which simplifies to O(n) when n >> C.

The space complexity is O(n) for storing the set ss, which contains at most n characters from the input string. However, since the set stores unique characters only, and there are at most 52 distinct letters (26 uppercase + 26 lowercase), the space complexity can also be expressed as O(min(n, C)) where C = 52. This effectively becomes O(C) when considering the bounded character set.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Compare Characters Directly Without Proper Ordering

A common mistake is trying to track the "greatest" letter while iterating through the string directly, which can lead to incorrect comparisons or complex logic.

Incorrect Approach:

def greatestLetter(self, s: str) -> str:
    greatest = ''
    for char in s:
        if char.upper() in s and char.lower() in s:
            if char.upper() > greatest:  # Bug: comparing with empty string initially
                greatest = char.upper()
    return greatest

Issue: This approach has multiple problems:

• Initial comparison with empty string can cause issues
• Inefficient repeated searches through the string
• May process the same letter multiple times

Solution: Use the reverse iteration approach shown in the original solution to naturally find the greatest letter first.

2. Forgetting to Return Uppercase Format

The problem specifically asks for the result in uppercase format, but it's easy to return the wrong case.

Incorrect:

if c in char_set and c.lower() in char_set:
    return c.lower()  # Wrong! Should return uppercase

Solution: Always return the uppercase version of the letter, even if you're checking for lowercase existence.

3. Using Inefficient String Search Instead of Set

Checking character existence directly in the string leads to O(n) lookup time for each check.

Inefficient Approach:

for c in ascii_uppercase[::-1]:
    if c in s and c.lower() in s:  # O(n) for each 'in' operation
        return c

Solution: Convert the string to a set first for O(1) lookup time:

char_set = set(s)
for c in ascii_uppercase[::-1]:
    if c in char_set and c.lower() in char_set:  # O(1) lookups
        return c

4. Not Handling Edge Cases Properly

Forgetting to return an empty string when no letter exists in both cases.

Incorrect:

def greatestLetter(self, s: str) -> str:
    char_set = set(s)
    for c in ascii_uppercase[::-1]:
        if c in char_set and c.lower() in char_set:
            return c
    # Missing return statement - will return None instead of ''

Solution: Explicitly return an empty string at the end of the function if no match is found.