LeetCode 2309 - Greatest English Letter in Upper and Lower Case

The problem gives us a string s containing only uppercase and lowercase English letters. Our task is to find the greatest English letter that appears in both lowercase and uppercase forms somewhere in the string. The answer must be returned as an uppercase letter.

leetcodeeasyhash-tablestringenumeration

LeetCode Problem 2309

Difficulty: 🟢 Easy
Topics: Hash Table, String, Enumeration

Solution

Problem Understanding

The problem gives us a string s containing only uppercase and lowercase English letters. Our task is to find the greatest English letter that appears in both lowercase and uppercase forms somewhere in the string. The answer must be returned as an uppercase letter.

To understand this clearly, consider what "greatest" means in this context. Letters are ordered alphabetically, so 'Z' is greater than 'Y', 'Y' is greater than 'X', and so on. We are not looking for the letter that appears most often or first in the string. We only care about alphabetical ranking.

For a letter to qualify, both versions of the same character must exist in the input. For example, if 'r' and 'R' both appear, then 'R' is a candidate. If only one version exists, such as 'e' without 'E', then it does not count.

The input is a single string s, where:

  • s.length ranges from 1 to 1000
  • s contains only uppercase and lowercase English letters

The output is:

  • The uppercase version of the greatest valid letter, if one exists
  • An empty string "" if no letter appears in both forms

The constraint of at most 1000 characters tells us that performance is not extremely demanding. Even less efficient approaches could pass, but we should still aim for a clean and optimal solution.

Several edge cases are worth identifying upfront. The string may contain only lowercase or only uppercase letters, meaning no valid answer exists. There may be multiple valid letters, in which case we must return the alphabetically largest one. Duplicate characters are possible, but frequency does not matter, only presence. Finally, the best answer may not appear near the end of the string, so relying on traversal order alone could produce incorrect results.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to check every English letter from 'A' through 'Z', and determine whether both uppercase and lowercase versions appear in the string.

One naive implementation would repeatedly scan the string for each letter. For example, we could check whether 'A' and 'a' exist, then 'B' and 'b', continuing until 'Z'. Any valid letters would be tracked, and the greatest one would be returned.

This approach is correct because it exhaustively evaluates every possible English letter and verifies the required condition directly. Since there are only 26 letters, it remains reasonably fast for the given constraints.

However, repeatedly searching the string introduces unnecessary repeated work. Every membership check may scan the string again, making the algorithm less efficient than needed.

Optimal Approach, Hash Set + Reverse Alphabet Traversal

The key observation is that we only care about whether characters exist, not how many times they appear. This immediately suggests using a hash set, because sets provide fast membership checks.

We can place all characters from s into a set. Then, instead of searching for candidates in arbitrary order, we iterate from 'Z' down to 'A'. For each uppercase letter, we check whether:

  1. The uppercase letter exists in the set
  2. The lowercase version also exists in the set

The first letter that satisfies both conditions is automatically the greatest valid answer because we search in descending alphabetical order.

This works especially well because the English alphabet has a fixed size of only 26 letters. After building the set once, the rest of the work is constant time.

Approach Time Complexity Space Complexity Notes
Brute Force O(26 × n) O(1) Repeatedly scans the string for each letter
Optimal O(n) O(n) Uses a hash set for constant time membership checks

Algorithm Walkthrough

  1. Create a hash set containing every character in the input string. This allows constant time lookup for whether a letter exists.
  2. Iterate through uppercase letters from 'Z' down to 'A'. We go in descending order because the first valid letter found will automatically be the greatest one.
  3. For each uppercase letter:
  • Check if the uppercase version exists in the set.
  • Convert it to lowercase and check if that version also exists.
  1. If both versions are present, immediately return the uppercase letter because it is the largest valid answer.
  2. If the loop finishes without finding a valid letter, return an empty string.

Why it works

The algorithm works because the set accurately captures the presence of every character in the input string. By iterating from 'Z' to 'A', we guarantee that the first valid match is the alphabetically greatest one. Since every possible candidate letter is checked exactly once, no valid answer can be missed, and no smaller answer can be returned before a larger one.

Python Solution

class Solution:
    def greatestLetter(self, s: str) -> str:
        characters = set(s)

        for ascii_code in range(ord('Z'), ord('A') - 1, -1):
            uppercase_letter = chr(ascii_code)
            lowercase_letter = uppercase_letter.lower()

            if (
                uppercase_letter in characters
                and lowercase_letter in characters
            ):
                return uppercase_letter

        return ""

The implementation begins by converting the string into a set named characters. Since duplicates are irrelevant, the set efficiently stores only unique characters while allowing constant time membership checks.

The loop iterates through ASCII values from 'Z' to 'A'. For each uppercase letter, we compute its lowercase counterpart using .lower(). We then check whether both forms exist in the set.

As soon as a valid letter is found, it is returned immediately. Since we traverse from largest to smallest, this early return guarantees correctness. If the loop completes without finding any match, the function returns an empty string.

Go Solution

func greatestLetter(s string) string {
	characters := make(map[rune]bool)

	for _, ch := range s {
		characters[ch] = true
	}

	for ch := 'Z'; ch >= 'A'; ch-- {
		lowercase := ch + ('a' - 'A')

		if characters[ch] && characters[lowercase] {
			return string(ch)
		}
	}

	return ""
}

The Go implementation uses a map[rune]bool to simulate a hash set. Each character from the string is inserted into the map for constant time lookup.

Unlike Python, Go does not have a direct .lower() method for a rune. Instead, we compute the lowercase equivalent using ASCII arithmetic by adding the difference between 'a' and 'A'.

Since English letters are ASCII characters and the problem guarantees only English letters, this conversion is safe and efficient.

Worked Examples

Example 1

Input:

s = "lEeTcOdE"

First, construct the set:

{'l', 'E', 'e', 'T', 'c', 'O', 'd'}

We iterate from 'Z' downward.

Current Letter Uppercase Exists? Lowercase Exists? Result
Z No No Continue
Y No No Continue
... ... ... Continue
T Yes No (t) Continue
O Yes No (o) Continue
E Yes Yes (e) Return "E"

Final answer:

"E"

Example 2

Input:

s = "arRAzFif"

Construct the set:

{'a', 'r', 'R', 'A', 'z', 'F', 'i', 'f'}

Traverse from 'Z' downward:

Current Letter Uppercase Exists? Lowercase Exists? Result
Z No Yes Continue
Y No No Continue
... ... ... Continue
R Yes Yes (r) Return "R"

Final answer:

"R"

Example 3

Input:

s = "AbCdEfGhIjK"

Construct the set:

{'A', 'b', 'C', 'd', 'E', 'f', 'G', 'h', 'I', 'j', 'K'}

Checking all letters from 'Z' to 'A', no uppercase letter has a corresponding lowercase version.

Final answer:

""

Complexity Analysis

Measure Complexity Explanation
Time O(n) Building the set takes O(n), checking 26 letters is constant time
Space O(n) The hash set stores characters from the string

The dominant cost comes from constructing the set of characters, which requires iterating through the string once. The second phase checks only 26 letters, which is constant time and does not scale with input size. Therefore, the total complexity is linear in the length of the string.

The space complexity is O(n) because, in the worst case, the set stores all distinct characters from the input. Since only English letters are allowed, this is effectively bounded by 52 unique values, but O(n) is the standard complexity classification.

Test Cases

solution = Solution()

assert solution.greatestLetter("lEeTcOdE") == "E"  # Example 1
assert solution.greatestLetter("arRAzFif") == "R"  # Example 2
assert solution.greatestLetter("AbCdEfGhIjK") == ""  # Example 3

assert solution.greatestLetter("aA") == "A"  # Smallest valid input pair
assert solution.greatestLetter("zZ") == "Z"  # Greatest possible letter
assert solution.greatestLetter("abc") == ""  # Only lowercase letters
assert solution.greatestLetter("ABC") == ""  # Only uppercase letters
assert solution.greatestLetter("aAbBcC") == "C"  # Multiple valid letters
assert solution.greatestLetter("AaBbYyZ") == "Y"  # Missing lowercase z
assert solution.greatestLetter("xXxXxX") == "X"  # Repeated characters
assert solution.greatestLetter("mMnNoOpP") == "P"  # Multiple consecutive pairs
assert solution.greatestLetter("aBcDeFgHiJkLmNoPqRsTuVwXyZ") == ""  # No matching cases
Test Why
"lEeTcOdE" Validates Example 1
"arRAzFif" Validates Example 2
"AbCdEfGhIjK" Validates Example 3
"aA" Tests smallest valid pair
"zZ" Ensures greatest letter handling
"abc" Verifies lowercase-only input
"ABC" Verifies uppercase-only input
"aAbBcC" Confirms greatest among multiple valid letters
"AaBbYyZ" Ensures incomplete pairs are ignored
"xXxXxX" Handles repeated characters correctly
"mMnNoOpP" Tests several valid candidates
Mixed alternating case string Verifies empty result when no pairs exist

Edge Cases

No Valid Letter Exists

A common edge case occurs when no character appears in both lowercase and uppercase forms. For example, "abc" or "ABC" contains only one case type. A naive implementation might accidentally return a partial match or an incorrect default value. Our implementation handles this correctly by checking all letters and returning an empty string if no valid pair is found.

Multiple Valid Candidates

The input may contain several letters that qualify. For example, "aAbBcC" contains valid pairs for A, B, and C. A buggy implementation might return the first valid match encountered in the string rather than the alphabetically greatest one. By iterating from 'Z' to 'A', our solution guarantees that the largest valid letter is returned.

Repeated Characters

The string may contain repeated occurrences of the same character, such as "xXxXxX". Frequency is irrelevant because the problem only asks whether both forms exist. Using a set naturally eliminates duplicates and prevents unnecessary repeated checks, making the implementation both simpler and more efficient.

Missing One Half of a Pair

A subtle case occurs when only one form of a high-ranking letter exists. For example, "AaBbYyZ" includes uppercase Z but no lowercase z. An incorrect implementation might mistakenly return Z simply because it is the largest letter present. Our solution explicitly checks for both uppercase and lowercase membership before returning a result, ensuring correctness.