Greatest English Letter in Upper and Lower Case

easy string hash set

Problem

Given a string s of English letters, return the greatest letter that appears as both its lowercase and uppercase form in s. The greatest letter is the one closest to the end of the alphabet. If no such letter exists, return an empty string. The returned letter should be in uppercase.

Inputs = "lEeTcOdE"

Output"E"

The letter 'E' is the only one present as both 'e' and 'E'.

def greatest_letter(s):
    seen = set(s)
    best = ""
    for i in range(25, -1, -1):
        lo = chr(ord('a') + i)
        up = chr(ord('A') + i)
        if lo in seen and up in seen:
            return up
    return best

function greatestLetter(s) {
  const seen = new Set(s);
  for (let i = 25; i >= 0; i--) {
    const lo = String.fromCharCode(97 + i);
    const up = String.fromCharCode(65 + i);
    if (seen.has(lo) && seen.has(up)) {
      return up;
    }
  }
  return "";
}

class Solution {
    public String greatestLetter(String s) {
        Set<Character> seen = new HashSet<>();
        for (char c : s.toCharArray()) seen.add(c);
        for (int i = 25; i >= 0; i--) {
            char lo = (char) ('a' + i);
            char up = (char) ('A' + i);
            if (seen.contains(lo) && seen.contains(up)) {
                return String.valueOf(up);
            }
        }
        return "";
    }
}

string greatestLetter(string s) {
    unordered_set<char> seen(s.begin(), s.end());
    for (int i = 25; i >= 0; i--) {
        char lo = 'a' + i;
        char up = 'A' + i;
        if (seen.count(lo) && seen.count(up)) {
            return string(1, up);
        }
    }
    return "";
}

Explanation

We want the letter nearest the end of the alphabet that shows up in both cases. The cleanest setup is to dump every character of s into a hash set so that "is this character present?" becomes an instant O(1) lookup.

Then we check the alphabet from 'z'/'Z' down to 'a'/'A'. Iterating from the top means the very first letter that qualifies is automatically the greatest, so we can return immediately.

For each index i (25 down to 0) we form the lowercase letter lo and the uppercase letter up for that position. If the set contains both, that letter exists in both cases and we return its uppercase form up.

If the loop completes without any letter qualifying, no letter appears in both cases, so we return the empty string.

Example: s = "lEeTcOdE". Scanning down from 'z', the first letter present as both lowercase and uppercase is e/E, so the answer is "E".

Time: O(n + 26) Space: O(1)