algoadvance

Given a string s of English letters, 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.

Example 1:

• Input: s = "lEeTcOdE"
• Output: "E"

Example 2:

• Input: s = "arRAzFif"
• Output: "R"

Example 3:

• Input: s = "AbCdEfGhIjK"
• Output: ""

Clarifying Questions:

1. What is the length of the string?
   The length of the string s can vary but will be constrained by typical LeetCode input limits (usually up to (10^5)).

2. Is the string case-sensitive initially?
   Yes, the string contains both uppercase and lowercase English letters and is case-sensitive initially.

3. What should be returned if there are multiple valid letters?
   The greatest letter (lexicographically) occurring in both cases should be returned in uppercase.

4. Are there any constraints on the contents of the string?
   The string s consists only of English letters.

Strategy:

1. Utilize Sets for Lookup:
   • Store the characters seen in the string using a set for O(1) average-time complexity lookups.
2. Iterate and Compare:
   • Iterate through the alphabet from ‘Z’ to ‘A’.
   • Check if both the uppercase and lowercase versions of each letter are in the set.
   • Return the first such letter found.
3. Return Default:
   • If no matching letter is found throughout the iteration, return an empty string.

This approach ensures we check for the lexicographically greatest letter due to the reverse iteration through the alphabet.

Code:

def greatestLetter(s: str) -> str:
    seen = set(s)
    
    for char in range(ord('Z'), ord('A') - 1, -1):
        upper = chr(char)
        lower = chr(char + 32)  # ASCII difference between uppercase and lowercase
        if upper in seen and lower in seen:
            return upper
            
    return ""

# Test cases
print(greatestLetter("lEeTcOdE"))  # Output: "E"
print(greatestLetter("arRAzFif"))  # Output: "R"
print(greatestLetter("AbCdEfGhIjK"))  # Output: ""

Time Complexity:

• Time Complexity: O(n + 26), which simplifies to O(n), where n is the length of the string. This results from the initial O(n) time to populate the set and the constant time O(26) to iterate from ‘Z’ to ‘A’.
• Space Complexity: O(n) due to storing the characters of the string in the set.

This solution ensures efficient performance even for large input sizes.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?