Greatest English Letter in Upper and Lower Case
EasyPrompt
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 <= 1000sconsists of lowercase and uppercase English letters.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses nested loops to compare every character in the string with every other character. It checks if any pair of characters represents the same letter in both lowercase and uppercase. It keeps track of the largest such letter found.
Algorithm
- Initialize a variable
greatestLetterto an empty string. - Use a nested loop to iterate through all pairs of characters
(c1, c2)in the input strings. - For each pair, check if one character is the lowercase version and the other is the uppercase version of the same letter (e.g.,
c1 == 'a'andc2 == 'A'). - If they are a pair, get the uppercase version of the letter.
- Compare this uppercase letter with the current
greatestLetter. If it's alphabetically greater, updategreatestLetter. - After checking all pairs, return the final
greatestLetter.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We initialize an empty string result which will store our answer. We then iterate through the input string s with an outer loop, and for each character, we start another inner loop to compare it with every character in the string. Inside the inner loop, we check if the two characters form a valid pair (e.g., 'e' and 'E'). We can do this by checking if one is lowercase, the other is uppercase, and their uppercase forms are identical. If a valid pair is found, we take its uppercase letter and check if it's greater than the one currently stored in result. If it is, we update result. This process continues until all pairs have been checked, ensuring we find the overall greatest letter.
class Solution { public String greatestLetter(String s) { String result = ""; for (int i = 0; i < s.length(); i++) { for (int j = 0; j < s.length(); j++) { char c1 = s.charAt(i); char c2 = s.charAt(j); // Check if c1 is lowercase and c2 is its uppercase counterpart if (Character.isLowerCase(c1) && Character.isUpperCase(c2) && Character.toUpperCase(c1) == c2) { String currentLetter = String.valueOf(c2); // Update result if it's the first one found or greater than the current result if (result.isEmpty() || currentLetter.compareTo(result) > 0) { result = currentLetter; } } } } return result; }}Complexity
Time
O(N^2), where N is the length of the string `s`. The nested loops lead to a quadratic runtime, as each character is compared with every other character.
Space
O(1), as we only use a few variables to store the result and loop indices, regardless of the input string's size.
Trade-offs
Pros
Simple to conceptualize and implement without requiring any special data structures.
Cons
Very inefficient due to the O(N^2) time complexity.
Impractical for large input strings.
A more optimized approach involves using a HashSet to store all the characters present in the string. This allows for very fast O(1) average time complexity for checking the existence of a character. By pre-processing the string into a set, we avoid repeated scanning.
Algorithm
- Create a
HashSet<Character>. - Iterate through the input string
sand add each character to theHashSet. This will store all unique characters from the string. - Iterate through the alphabet from 'Z' down to 'A'.
- For each uppercase letter
ch, check if bothchand its lowercase versionCharacter.toLowerCase(ch)exist in theHashSet. - The first letter that satisfies this condition is the greatest one (since we are iterating in reverse alphabetical order). Return it as a string.
- If the loop completes without finding such a letter, return an empty string.
Walkthrough
We can significantly improve performance by first creating a set of all characters in the string. We iterate through the string s once and populate a HashSet. This takes O(N) time. After building the set, we no longer need to scan the original string. Instead, we can iterate through the 26 letters of the alphabet, from 'Z' down to 'A'. For each letter, we check if both its uppercase and lowercase forms are present in our set. Since lookups in a HashSet are very fast (O(1) on average), this checking step is highly efficient. The first letter we find that satisfies this condition will be the greatest one, so we can return it immediately. If we finish the loop, no such letter exists.
import java.util.HashSet;import java.util.Set; class Solution { public String greatestLetter(String s) { Set<Character> charSet = new HashSet<>(); for (char c : s.toCharArray()) { charSet.add(c); } for (char ch = 'Z'; ch >= 'A'; ch--) { if (charSet.contains(ch) && charSet.contains(Character.toLowerCase(ch))) { return String.valueOf(ch); } } return ""; }}Complexity
Time
O(N), where N is the length of the string `s`. It takes O(N) to populate the set, and the subsequent loop runs a constant 26 times with O(1) lookups.
Space
O(K), where K is the number of unique characters. Since the input is limited to English letters, the maximum number of unique characters is 52. Thus, the space complexity is effectively O(1) or constant space.
Trade-offs
Pros
Significantly faster than the brute-force approach with O(N) time complexity.
The logic is clean and easy to understand.
Cons
Incurs a small overhead from using a hash-based data structure (e.g., memory for the hash table, computation for hash codes).
This approach refines the HashSet method by using simple boolean arrays for tracking character presence. Since we are only dealing with English letters, we can use two arrays of size 26 as direct-access tables, which is generally faster and more memory-efficient than a HashSet.
Algorithm
- Create two boolean arrays of size 26,
lowerPresentandupperPresent, initialized tofalse. - Iterate through the input string
sonce. - For each character
c, if it's lowercase, setlowerPresent[c - 'a'] = true. If it's uppercase, setupperPresent[c - 'A'] = true. - After populating the arrays, iterate from
i = 25down to0(representing 'Z' to 'A'). - In each iteration, check if
lowerPresent[i]andupperPresent[i]are bothtrue. - If they are, this is the greatest letter. Return
(char)('A' + i)as a string. - If the loop finishes, return an empty string.
Walkthrough
Instead of a HashSet, we can use two boolean arrays, lowerPresent and upperPresent, each of size 26, to track the presence of lowercase and uppercase letters, respectively. We make a single pass through the input string s. For each character, we determine if it's lowercase or uppercase and update the corresponding boolean array at the appropriate index (e.g., for 'c', we set lowerPresent[2] = true). This pass takes O(N) time. Afterwards, we iterate from 25 down to 0. The index i corresponds to the i-th letter of the alphabet. We check if lowerPresent[i] and upperPresent[i] are both true. The first index i for which this is true corresponds to the greatest letter that exists in both cases. We can then construct this character and return it. This method avoids the overhead of hashing.
class Solution { public String greatestLetter(String s) { boolean[] lowerPresent = new boolean[26]; boolean[] upperPresent = new boolean[26]; for (char c : s.toCharArray()) { if (c >= 'a' && c <= 'z') { lowerPresent[c - 'a'] = true; } else if (c >= 'A' && c <= 'Z') { upperPresent[c - 'A'] = true; } } for (int i = 25; i >= 0; i--) { if (lowerPresent[i] && upperPresent[i]) { return String.valueOf((char)('A' + i)); } } return ""; }}Complexity
Time
O(N), where N is the length of the string. This consists of one pass over the string (O(N)) and one pass over the 26-element arrays (O(1)).
Space
O(1), as it uses two fixed-size arrays of 26 booleans, which does not depend on the input size.
Trade-offs
Pros
Highly efficient in both time and space.
Faster than the
HashSetapproach due to direct array access instead of hashing.
Cons
This approach is specifically tailored to a fixed character set like the English alphabet and is less general than a
HashSet.
The most optimized solution in terms of memory and speed uses bit manipulation. We can represent the presence of the 26 lowercase and 26 uppercase letters using two integers as bitmasks. Bitwise operations are extremely fast, making this a highly efficient approach.
Algorithm
- Initialize two integer variables,
lowerMaskandupperMask, to 0. - Iterate through the input string
s. - For each character
c:- If
cis lowercase, set the(c - 'a')-th bit inlowerMaskusing the bitwise OR operation:lowerMask |= (1 << (c - 'a')). - If
cis uppercase, set the(c - 'A')-th bit inupperMask:upperMask |= (1 << (c - 'A')).
- If
- After the loop, perform a bitwise AND between the two masks:
commonMask = lowerMask & upperMask. The resulting mask will have bits set for letters that appeared in both cases. - Find the most significant bit (MSB) in
commonMask. This can be done by looping from 25 down to 0. - If a set bit
iis found,(char)('A' + i)is the answer. - If
commonMaskis 0, no such letter exists, so return an empty string.
Walkthrough
This approach leverages the fact that there are only 26 English letters, which can be represented by the bits of an integer. We use two integers, lowerMask and upperMask, to act as bitmasks. We iterate through the string s once. For each character, we calculate its corresponding bit position (0 for 'a'/'A', 1 for 'b'/'B', etc.) and set that bit in the appropriate mask using a bitwise OR. After this single pass, we have two masks summarizing all the letters present. A simple bitwise AND (&) on these two masks gives us a commonMask, where a bit is set only if the corresponding letter was present in both lowercase and uppercase. Finally, we find the highest set bit in commonMask. We can do this by looping from 25 down to 0 and checking the bit at each position. The first one we find corresponds to the greatest letter.
class Solution { public String greatestLetter(String s) { int lowerMask = 0; int upperMask = 0; for (char c : s.toCharArray()) { if (Character.isLowerCase(c)) { lowerMask |= (1 << (c - 'a')); } else if (Character.isUpperCase(c)) { upperMask |= (1 << (c - 'A')); } } int commonMask = lowerMask & upperMask; for (int i = 25; i >= 0; i--) { if ((commonMask & (1 << i)) != 0) { return String.valueOf((char)('A' + i)); } } return ""; }}Complexity
Time
O(N), where N is the length of the string. It involves a single pass over the string and a small, constant-time loop (26 iterations).
Space
O(1). The space required is constant as it only uses a few integer variables.
Trade-offs
Pros
Extremely fast due to the use of low-level bitwise operations.
Minimal memory usage, requiring only two integers for storage.
Cons
The logic can be less intuitive for developers not comfortable with bitwise operations.
Solutions
Solution
class Solution {public String greatestLetter(String s) { Set<Character> ss = new HashSet<>(); for (char c : s.toCharArray()) { ss.add(c); } for (char a = 'Z'; a >= 'A'; --a) { if (ss.contains(a) && ss.contains((char)(a + 32))) { return String.valueOf(a); } } return ""; }}/** * @param {string} s * @return {string} */ var greatestLetter = function ( s ) { const ss = new Array ( 128 ). fill ( false ); for ( const c of s ) { ss [ c . charCodeAt ( 0 )] = true ; } for ( let i = 90 ; i >= 65 ; -- i ) { if ( ss [ i ] && ss [ i + 32 ]) { return String . fromCharCode ( i ); } } return '' ; };class Solution {public: string greatestLetter(string s) { unordered_set<char> ss(s.begin(), s.end()); for (char c = 'Z'; c >= 'A'; --c) { if (ss.count(c) && ss.count(char(c + 32))) { return string(1, c); } } return ""; }};class Solution: def greatestLetter(self, s: str) -> str: ss = set(s) for c in ascii_uppercase[:: - 1]: if c in ss and c . lower() in ss: return c return ''Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.