Problem

Given a string of English letters s, return thegreatest 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.

Examples

Example 1

1
2
3
4

Input: s = "l** _Ee_** TcOd _**E**_ "
Output: "E"
Explanation:
The letter 'E' is the only letter to appear in both lower and upper case.

Example 2

1
2
3
4
5

Input: s = "a** _rR_** AzFif"
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

1
2
3
4

Input: s = "AbCdEfGhIjK"
Output: ""
Explanation:
There is no letter that appears in both lower and upper case.

Constraints

  • 1 <= s.length <= 1000
  • s consists of lowercase and uppercase English letters.

Solution

Method 1 – Set Membership and Reverse Alphabet

Intuition

We want the greatest English letter that appears in both lowercase and uppercase in the string. By collecting all lowercase and uppercase letters, we can check from ‘Z’ to ‘A’ if both cases exist for a letter.

Approach

  1. Create sets for all lowercase and uppercase letters in the string.
  2. Iterate from ‘Z’ to ‘A’.
  3. For each letter, check if both the uppercase and lowercase forms are present in the string.
  4. Return the first such letter found, or an empty string if none exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    string greatestLetter(string s) {
        set<char> st(s.begin(), s.end());
        for (char c = 'Z'; c >= 'A'; --c) {
            if (st.count(c) && st.count(c + 32)) return string(1, c);
        }
        return "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func greatestLetter(s string) string {
    lower, upper := make(map[rune]bool), make(map[rune]bool)
    for _, c := range s {
        if c >= 'a' && c <= 'z' {
            lower[c] = true
        } else if c >= 'A' && c <= 'Z' {
            upper[c] = true
        }
    }
    for c := 'Z'; c >= 'A'; c-- {
        if upper[c] && lower[c+32] {
            return string(c)
        }
    }
    return ""
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public String greatestLetter(String s) {
        boolean[] lower = new boolean[26], upper = new boolean[26];
        for (char c : s.toCharArray()) {
            if (c >= 'a' && c <= 'z') lower[c - 'a'] = true;
            if (c >= 'A' && c <= 'Z') upper[c - 'A'] = true;
        }
        for (char c = 'Z'; c >= 'A'; c--) {
            if (upper[c - 'A'] && lower[c - 'A']) return String.valueOf(c);
        }
        return "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun greatestLetter(s: String): String {
        val lower = BooleanArray(26)
        val upper = BooleanArray(26)
        for (c in s) {
            if (c in 'a'..'z') lower[c - 'a'] = true
            if (c in 'A'..'Z') upper[c - 'A'] = true
        }
        for (c in 'Z' downTo 'A') {
            if (upper[c - 'A'] && lower[c - 'A']) return c.toString()
        }
        return ""
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def greatestLetter(self, s: str) -> str:
        lower = set()
        upper = set()
        for c in s:
            if c.islower():
                lower.add(c)
            elif c.isupper():
                upper.add(c)
        for c in reversed('ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
            if c in upper and c.lower() in lower:
                return c
        return ""
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn greatest_letter(s: String) -> String {
        let mut lower = [false; 26];
        let mut upper = [false; 26];
        for b in s.bytes() {
            if b >= b'a' && b <= b'z' {
                lower[(b - b'a') as usize] = true;
            } else if b >= b'A' && b <= b'Z' {
                upper[(b - b'A') as usize] = true;
            }
        }
        for i in (0..26).rev() {
            if lower[i] && upper[i] {
                return ((b'A' + i as u8) as char).to_string();
            }
        }
        String::new()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    greatestLetter(s: string): string {
        const lower = new Set<string>(), upper = new Set<string>();
        for (const c of s) {
            if (c >= 'a' && c <= 'z') lower.add(c);
            if (c >= 'A' && c <= 'Z') upper.add(c);
        }
        for (let i = 25; i >= 0; i--) {
            const up = String.fromCharCode(65 + i), lo = String.fromCharCode(97 + i);
            if (upper.has(up) && lower.has(lo)) return up;
        }
        return "";
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each character is visited once, and the alphabet is checked in constant time.
  • 🧺 Space complexity: O(1) — Only fixed-size sets or arrays are used.