Problem Description

The "Greatest English Letter in Upper and Lower Case" problem requires you to find the greatest English letter (alphabet character) that appears in both its uppercase and lowercase forms in a given string s.

• You are given a string s consisting of English letters (both uppercase and lowercase).
• You must find the greatest English letter (in lexicographical order, i.e., 'Z' > 'Y' > ... > 'A') that appears in both uppercase and lowercase in s.
• Return the uppercase form of that letter as a string. If no such letter exists, return an empty string "".

Constraints:

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

Thought Process

The problem asks us to find the "greatest" (largest in the alphabet) English letter that is present in both uppercase and lowercase forms in the string. At first glance, one might think to check every letter from 'A' to 'Z' and see if both cases exist in the string. However, a brute-force approach would require checking each letter for both cases, which could be inefficient if not handled properly.

A more efficient way is to use sets to quickly check for the existence of uppercase and lowercase letters. By storing all characters in the string in a set, we can check for the presence of both cases for each letter in constant time. To ensure we find the "greatest" letter, we can iterate from 'Z' down to 'A', and return as soon as we find a letter that meets the criteria.

This approach avoids unnecessary repeated scans and leverages fast lookups, making it much more optimal than brute-force.

Solution Approach

Let's break down the solution into clear steps:

1. Store all characters: Place all characters from s into a set. This allows O(1) lookups to check if a character exists in the string.
2. Iterate from 'Z' to 'A': For each uppercase letter from 'Z' down to 'A', check if both the uppercase and its corresponding lowercase letter exist in the set.
3. Return the first match: As soon as you find a letter where both cases are present, return the uppercase letter as a string.
4. No match case: If no such letter is found after the loop, return an empty string "".

Why use a set? Sets allow us to check for the existence of a character in constant time. This is much faster than searching through the string each time.

Why iterate from 'Z' to 'A'? Since we want the greatest letter, we start from the end of the alphabet and return as soon as we find a match.

Example Walkthrough

Let's consider the input s = "lEeTcOdE".

• Step 1: Put all characters into a set: {'l', 'E', 'e', 'T', 'c', 'O', 'd'}
• Step 2: Start from 'Z' and check down to 'A':
  • Check 'Z': 'Z' and 'z' not present.
  • Check 'Y': 'Y' and 'y' not present.
  • ... (continue down) ...
  • Check 'O': 'O' is present but 'o' is not.
  • Check 'E': 'E' is present and 'e' is present!
• Step 3: Return 'E' since both 'E' and 'e' are present.

Output: "E"

Code Implementation

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

class Solution {
public:
    string greatestLetter(string s) {
        unordered_set<char> letters(s.begin(), s.end());
        for (char c = 'Z'; c >= 'A'; --c) {
            if (letters.count(c) && letters.count(c + 32)) {
                return string(1, c);
            }
        }
        return "";
    }
};
      

class Solution {
    public String greatestLetter(String s) {
        HashSet<Character> letters = new HashSet<>();
        for (char ch : s.toCharArray()) {
            letters.add(ch);
        }
        for (char c = 'Z'; c >= 'A'; --c) {
            if (letters.contains(c) && letters.contains((char)(c + 32))) {
                return String.valueOf(c);
            }
        }
        return "";
    }
}
      

var greatestLetter = function(s) {
    const letters = new Set(s);
    for (let code = 90; code >= 65; code--) { // 'Z' to 'A'
        const upper = String.fromCharCode(code);
        const lower = String.fromCharCode(code + 32);
        if (letters.has(upper) && letters.has(lower)) {
            return upper;
        }
    }
    return "";
};
      

Time and Space Complexity

Brute-force approach: For each letter from 'A' to 'Z', scan the string twice (once for uppercase, once for lowercase), resulting in O(26 * n), where n is the length of s.

Optimized approach:

• Building the set takes O(n) time and O(n) space.
• Iterating from 'Z' to 'A' is O(1) since it's always 26 iterations.
• Each lookup in the set is O(1).
• Total time complexity: O(n)
• Total space complexity: O(n)

Summary

The solution efficiently finds the greatest English letter present in both upper and lower case by leveraging a set for fast existence checks and iterating from 'Z' to 'A' to ensure the greatest is found first. This approach is both simple and optimal, demonstrating the power of set-based lookups and careful iteration order in algorithm design.