Greatest English Letter in Upper and Lower Case — Solution
Greatest English Letter in Upper and Lower Case solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Greatest English Letter in Upper and Lower Case is an easy coding problem on strings, hash table and enumeration, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Strings, Hash Table, Enumeration
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The string s contains English letters in both cases.
Among the letters that appear in s both as a lowercase letter and as an uppercase letter, find the one that comes latest in the alphabet and return it as an uppercase one-character string. If no letter appears in both cases, return the empty string "".
Example 1
Input: s = "KaiRoKAIro"
Output: R
Explanation: A, I and R appear in both cases; R is the greatest.
Example 2
Input: s = "codeKAIRO"
Output: O
Example 3
Input: s = "Bug"
Output: ""
Explanation: No letter appears in both cases, so the answer is the empty string.
Constraints
1 <= s.length <= 1000s consists of lowercase and uppercase English letters
Hints for Greatest English Letter in Upper and Lower Case
Hint 1
Record which lowercase letters and which uppercase letters occur.
Hint 2
Two arrays of 26 flags (or one set of characters) are enough.
Hint 3
Check the letters from
Zdown toAand return the first one present in both cases.
How to solve Greatest English Letter in Upper and Lower Case
Mark the letters seen in each case, then scan the alphabet from the top; the first letter marked in both cases is the greatest.
Approach
- Create flags
lower[26]andupper[26]. - For each character set the flag of its case.
- For
cfrom 25 down to 0, iflower[c]andupper[c], return the uppercase letter'A' + c. - Return
""if the scan finds nothing.
Why it works
The flags record exactly which letters occur in which case, and scanning from Z downward returns the largest qualifying letter first. The answer is required in uppercase, which is what is returned.
Complexity
- Time —
O(n + 26) - Space —
O(1)
Pitfalls
- Return the uppercase form even though the letter also appears in lowercase.
- Compare letters by alphabet position, not by raw character codes across cases (every uppercase code is smaller than every lowercase one).
- Return the empty string, not a space or null, when no letter qualifies.
Reference solution
Python
def greatestLetter(s: str) -> str:
present = set(s)
for c in reversed('ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
if c in present and c.lower() in present:
return c
return ""Java
public static String greatestLetter(String s) {
boolean[] lower = new boolean[26], upper = new boolean[26];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c >= 'a') lower[c - 'a'] = true;
else upper[c - 'A'] = true;
}
for (int k = 25; k >= 0; k--) {
if (lower[k] && upper[k]) return String.valueOf((char) ('A' + k));
}
return "";
}C++
string greatestLetter(string s) {
bool lower[26] = {false}, upper[26] = {false};
for (char c : s) {
if (c >= 'a') lower[c - 'a'] = true;
else upper[c - 'A'] = true;
}
for (int k = 25; k >= 0; k--) {
if (lower[k] && upper[k]) return string(1, (char)('A' + k));
}
return "";
}JavaScript
var greatestLetter = function(s) {
var lower = [], upper = [];
for (var z = 0; z < 26; z++) { lower.push(false); upper.push(false); }
for (var i = 0; i < s.length; i++) {
var c = s.charCodeAt(i);
if (c >= 97) lower[c - 97] = true;
else upper[c - 65] = true;
}
for (var k = 25; k >= 0; k--) {
if (lower[k] && upper[k]) return String.fromCharCode(65 + k);
}
return "";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets