Given a string of English letters 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 letter a if b appears after a in the English alphabet.
Example 1:
Input: s = "lEeTcOdE" Output: "E" Explanation: The letter 'E' is the only letter to appear in both lower and upper case.
Example 2:
Input: s = "arRAzFif" Output: "R" Explanation: The letter 'R' is the greatest letter to appear in both lower and upper case. Note that 'A' and 'F' also appear in both lower and upper case, but 'R' is greater than 'F' or 'A'.
Example 3:
Input: s = "AbCdEfGhIjK" Output: "" Explanation: There is no letter that appears in both lower and upper case.
Constraints:
1 <= s.length <= 1000s consists of lowercase and uppercase English letters.Problem Overview: You receive a string containing uppercase and lowercase English letters. The task is to return the greatest alphabetical letter that appears in both uppercase and lowercase forms. If no such letter exists, return an empty string. For example, if both 'A' and 'a' appear, the candidate letter is 'A', and you must return the lexicographically greatest valid one.
Approach 1: Use Two Sets to Track Upper and Lower Case Letters (O(n) time, O(1) space)
This approach scans the string and stores characters in two hash table-style sets: one for lowercase letters and one for uppercase letters. Each iteration checks the character type and inserts it into the corresponding set. After building both sets, iterate from 'Z' down to 'A'. For each letter, check whether its lowercase counterpart exists in the lowercase set. The first match is the answer because the search moves from the greatest letter downward. The alphabet size is constant (26), so the additional scan is effectively constant time.
The key insight is separating uppercase and lowercase tracking so membership checks become O(1). This method is simple, readable, and maps directly to the problem statement. Space complexity is technically O(1) because at most 26 letters are stored in each set.
Approach 2: Single Pass with Boolean Tracking Arrays (O(n) time, O(1) space)
This optimized variant replaces sets with two fixed-size boolean arrays of length 26. While iterating through the string, mark whether each lowercase or uppercase letter has been seen. For example, when encountering 'a', set lower[0] = true; when encountering 'A', set upper[0] = true. After processing the string, iterate backward from index 25 to 0 and check where both arrays contain true. The first such index corresponds to the greatest valid letter.
This approach removes hashing overhead and uses direct indexing based on ASCII offsets. Because the alphabet size is fixed, the memory footprint remains constant. The algorithm still performs a single linear pass through the string plus a constant 26-character scan. Problems involving limited character ranges often benefit from this pattern, especially in enumeration tasks.
Recommended for interviews: The boolean array approach is typically preferred because it demonstrates awareness of fixed-size constraints and efficient character indexing. The set-based approach is still perfectly valid and easier to implement quickly. Showing both indicates that you understand the straightforward solution and can optimize when the input domain allows constant-size structures.
In this approach, we utilize two sets to track the lowercase and uppercase letters present in the string. By iterating through the possible letters from 'Z' to 'A', we can determine if both the lowercase and uppercase of a letter exist in the sets. This ensures that we find the greatest such letter as we are iterating from the greatest possible letter.
This solution uses two sets to store lowercase and uppercase letters from the string. It then checks if both cases of a letter from 'Z' to 'A' are present in the sets to return the greatest letter. If none are found, an empty string is returned.
The time complexity is O(n), where n is the length of the string, due to iterating over it twice. The space complexity is O(1) as the size of the sets remains constant with only 26 possible lowercase and uppercase letters.
In this approach, we leverage two boolean arrays to track the presence of lowercase and uppercase letters in the string. We make one pass through the string to populate these arrays. Then, we check from 'Z' to 'A' to find the greatest letter that exists in both cases.
This solution uses two boolean arrays to track the presence of each letter case. Then, it checks from 'Z' to 'A' via the index to identify the greatest common letter.
The algorithm has a time complexity of O(n) for checking all characters, with space complexity O(1) for the fixed size arrays.
First, we use a hash table ss to record all the letters that appear in the string s. Then we start enumerating from the last letter of the uppercase alphabet. If both the uppercase and lowercase forms of the current letter are in ss, we return that letter.
At the end of the enumeration, if no letter that meets the conditions is found, we return an empty string.
The time complexity is O(n), and the space complexity is O(C). Here, n and C are the length of the string s and the size of the character set, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
We can use two integers mask1 and mask2 to record the lowercase and uppercase letters that appear in the string s, respectively. The i-th bit of mask1 indicates whether the i-th lowercase letter appears, and the i-th bit of mask2 indicates whether the i-th uppercase letter appears.
Then we perform a bitwise AND operation on mask1 and mask2. The i-th bit of the resulting mask indicates whether the i-th letter appears in both uppercase and lowercase.
Next, we just need to get the position of the highest 1 in the binary representation of mask, and convert it to the corresponding uppercase letter. If all binary bits are not 1, it means that there is no letter that appears in both uppercase and lowercase, so we return an empty string.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Use Two Sets to Track Upper and Lower Case Letters | The time complexity is O(n), where n is the length of the string, due to iterating over it twice. The space complexity is O(1) as the size of the sets remains constant with only 26 possible lowercase and uppercase letters. |
| Single Pass with Boolean Tracking Arrays | The algorithm has a time complexity of O(n) for checking all characters, with space complexity O(1) for the fixed size arrays. |
| Hash Table + Enumeration | — |
| Bit Manipulation (Space Optimization) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Sets for Uppercase and Lowercase | O(n) | O(1) | Best for clarity and quick implementation using hash lookups |
| Boolean Tracking Arrays | O(n) | O(1) | Preferred when character range is fixed (26 letters) and you want minimal overhead |
Complete Weekly Contest 298 | Leetcode 2309 Greatest English Letter in Upper and Lower Case 🔥🔥 • Coding Decoded • 934 views views
Watch 9 more video solutions →Practice Greatest English Letter in Upper and Lower Case with our built-in code editor and test cases.
Practice on FleetCode