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.
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 ""; }}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.