Greatest English Letter in Upper and Lower Case

Easy
1198.

Greatest English Letter in Upper and Lower Case

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.

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 <= 1000
  • s consists of lowercase and uppercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var greatestLetter = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • s consists of lowercase and uppercase English letters

Hints for Greatest English Letter in Upper and Lower Case

  1. Hint 1

    Record which lowercase letters and which uppercase letters occur.

  2. Hint 2

    Two arrays of 26 flags (or one set of characters) are enough.

  3. Hint 3

    Check the letters from Z down to A and 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

  1. Create flags lower[26] and upper[26].
  2. For each character set the flag of its case.
  3. For c from 25 down to 0, if lower[c] and upper[c], return the uppercase letter 'A' + c.
  4. 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