# Greatest English Letter in Upper and Lower Case
**Difficulty:** EASY
[External](https://leetcode.com/problems/greatest-english-letter-in-upper-and-lower-case)
Canonical: https://scaleengineer.com/dsa/problems/greatest-english-letter-in-upper-and-lower-case
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Hash Table, String
---
## Problem
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 = "l**Ee**TcOd**E**"
**Output:** "E"
**Explanation:**
The letter 'E' is the only letter to appear in both lower and upper case.

**Example 2:**

**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:**

**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.

# Approaches
## Brute-Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a variable `greatestLetter` to an empty string.
- Use a nested loop to iterate through all pairs of characters `(c1, c2)` in the input string `s`.
- 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'` and `c2 == '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, update `greatestLetter`.
- After checking all pairs, return the final `greatestLetter`.

## Using a Hash Set
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.
**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.
**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).
### Explanation
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.

```java
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 "";
    }
}
```
### Algorithm
- Create a `HashSet<Character>`.
- Iterate through the input string `s` and add each character to the `HashSet`. 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 both `ch` and its lowercase version `Character.toLowerCase(ch)` exist in the `HashSet`.
- 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.

## Using Boolean Arrays
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`.
**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.
**Pros:** Highly efficient in both time and space.; Faster than the `HashSet` approach 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`.
### Explanation
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.

```java
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 "";
    }
}
```
### Algorithm
- Create two boolean arrays of size 26, `lowerPresent` and `upperPresent`, initialized to `false`.
- Iterate through the input string `s` once.
- For each character `c`, if it's lowercase, set `lowerPresent[c - 'a'] = true`. If it's uppercase, set `upperPresent[c - 'A'] = true`.
- After populating the arrays, iterate from `i = 25` down to `0` (representing 'Z' to 'A').
- In each iteration, check if `lowerPresent[i]` and `upperPresent[i]` are both `true`.
- If they are, this is the greatest letter. Return `(char)('A' + i)` as a string.
- If the loop finishes, return an empty string.

## Bit Manipulation
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.
**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.
**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.
### Explanation
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.

```java
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 "";
    }
}
```
### Algorithm
- Initialize two integer variables, `lowerMask` and `upperMask`, to 0.
- Iterate through the input string `s`.
- For each character `c`:
  - If `c` is lowercase, set the `(c - 'a')`-th bit in `lowerMask` using the bitwise OR operation: `lowerMask |= (1 << (c - 'a'))`.
  - If `c` is uppercase, set the `(c - 'A')`-th bit in `upperMask`: `upperMask |= (1 << (c - 'A'))`.
- 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 `i` is found, `(char)('A' + i)` is the answer.
- If `commonMask` is 0, no such letter exists, so return an empty string.

# Solutions
### Java

```java
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 "";
  }
}

```

### JavaScript

```javascript
/** * @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 '' ; };
```

### CPP

```cpp
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 "";
  }
};

```

### Python

```python
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 ''

```