{x}
blog image

Greatest English Letter in Upper and Lower Case

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

Solution Explanation

This problem asks to find the greatest English letter that appears in both lowercase and uppercase within a given string. The solution involves iterating through the alphabet and checking for the presence of both uppercase and lowercase versions of each letter.

Approach 1: Hash Table and Enumeration

This approach uses a hash table (or set) to efficiently store the characters present in the input string. Then, it iterates through the alphabet from 'Z' to 'A', checking if both the uppercase and lowercase versions of each letter are in the hash table. The first such letter encountered is the greatest letter satisfying the condition.

Time Complexity: O(n + 26), where n is the length of the string. The hash table construction takes O(n) time, and iterating through the alphabet takes O(26) time, which is a constant. Overall, it's dominated by O(n).

Space Complexity: O(m), where m is the number of unique characters in the string (at most 52). The hash table stores these unique characters.

Approach 2: Bit Manipulation (Space Optimization)

This approach cleverly utilizes bit manipulation to reduce space complexity. It uses two integer variables, mask1 and mask2, to represent the presence of lowercase and uppercase letters respectively. Each bit in these integers corresponds to a letter in the alphabet. A bit is set to 1 if the corresponding letter is present in the string.

The algorithm then performs a bitwise AND operation (mask1 & mask2) to find letters present in both lowercase and uppercase. The highest set bit in the result indicates the greatest such letter.

Time Complexity: O(n), where n is the length of the string. The iteration through the string to set bits takes O(n) time, and finding the highest set bit using Integer.numberOfLeadingZeros or similar functions is O(1) in practice (though technically O(log n) in the worst case for a very large integer). The overall complexity is dominated by O(n).

Space Complexity: O(1). The approach uses only a few integer variables, regardless of the input string's size.

Code Examples

The code examples provided demonstrate both approaches in various programming languages. The key differences lie in how the hash table/set and bit manipulation are implemented, but the core logic remains consistent. For instance, in Python, sets are used naturally, while in Java, HashSet is used. Similarly, Java uses Integer.numberOfLeadingZeros for efficient finding of highest set bit, which is equivalent to bits.Len(uint(mask))-1 in Go. The other languages use the appropriate constructs available in each language for bit manipulation and set operations.

Note: The bit manipulation approach is generally more efficient in terms of space complexity, especially for very large input strings. However, the hash table approach might be easier to understand for programmers less familiar with bit manipulation techniques. The choice of approach often depends on the trade-off between space optimization and readability/maintainability.