Greatest English Letter in Upper and Lower Case

Difficulty: Easy | Acceptance: 72.00% | Paid: No Topics: Hash Table, String, Enumeration

Given a string 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 English letter a if b appears after a in the English alphabet.

• Examples
• Constraints
• Brute Force Enumeration
• Hash Set Approach
• Boolean Array Approach

Examples

Example 1:

Input: s = "arRAzFif"
Output: "R"
Explanation: The letter 'R' is the greatest letter that appears in both lower and upper case in s.

Example 2:

Input: s = "AbCdEfGhIjK"
Output: ""
Explanation: There is no letter that appears in both lower and upper case in s.

Example 3:

Input: s = "aA"
Output: "A"
Explanation: The letter 'A' is the greatest letter that appears in both lower and upper case in s.

Constraints

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

Brute Force Enumeration

Intuition Iterate from ‘Z’ down to ‘A’ and for each letter, check if both its uppercase and lowercase forms exist in the string.

Steps

• Iterate from ‘Z’ down to ‘A’
• For each letter, check if both uppercase and lowercase versions exist in the string
• Return the first letter found (which will be the greatest)
• If no letter is found, return an empty string

class Solution:
    def greatestLetter(self, s: str) -> str:
        for c in range(ord('Z'), ord('A') - 1, -1):
            upper = chr(c)
            lower = chr(c + 32)
            if upper in s and lower in s:
                return upper
        return ""

Complexity

• Time: O(26 * n) = O(n) where n is the length of the string
• Space: O(1)
• Notes: Simple but may have repeated string searches

Hash Set Approach

Intuition Store all characters in a hash set for O(1) lookup, then iterate from ‘Z’ to ‘A’ checking if both cases exist.

Steps

• Create a set containing all characters from the string
• Iterate from ‘Z’ down to ‘A’
• For each letter, check if both uppercase and lowercase versions are in the set
• Return the first letter found
• If no letter is found, return an empty string

class Solution:
    def greatestLetter(self, s: str) -> str:
        char_set = set(s)
        for c in range(ord('Z'), ord('A') - 1, -1):
            upper = chr(c)
            lower = chr(c + 32)
            if upper in char_set and lower in char_set:
                return upper
        return ""

Complexity

• Time: O(n) where n is the length of the string
• Space: O(n) for the hash set
• Notes: More efficient lookups but uses extra space

Boolean Array Approach

Intuition Use two boolean arrays of size 26 to track which uppercase and lowercase letters exist in the string.

Steps

• Create two boolean arrays of size 26 for uppercase and lowercase letters
• Iterate through the string and mark the presence of each letter
• Iterate from index 25 down to 0 (representing ‘Z’ to ‘A’)
• Check if both uppercase and lowercase versions exist for each letter
• Return the first letter found
• If no letter is found, return an empty string

class Solution:
    def greatestLetter(self, s: str) -> str:
        upper = [False] * 26
        lower = [False] * 26
        
        for c in s:
            if c.isupper():
                upper[ord(c) - ord('A')] = True
            else:
                lower[ord(c) - ord('a')] = True
        
        for i in range(25, -1, -1):
            if upper[i] and lower[i]:
                return chr(ord('A') + i)
        return ""

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) - fixed size arrays of 26
• Notes: Most space-efficient with constant space