2309. Greatest English Letter in Upper and Lower Case

EasyHash TableStringEnumeration

Problem Description

Given a string s consisting of English letters, the task is to find the largest letter (by the position in the alphabet) that exists both in lowercase and uppercase in the string s. The result should be the uppercase version of this letter. If there are no such letters that exist in both cases, return an empty string. The concept of being "larger" is determined by the standard order of letters in the English alphabet, meaning 'B' is greater than 'A', 'C' is greater than 'B', and so on up to 'Z'.

Intuition

For an efficient solution, one could use bit manipulation to keep track of which letters are present in the string s in both lowercase and uppercase forms. To do so, you can create two bit masks: one for lowercase letters (mask1) and one for uppercase letters (mask2). The idea is to use each bit in these masks to represent the presence of each letter in the alphabet— for example, the least significant bit would represent 'a' or 'A', the second least significant bit 'b' or 'B', and so on.

As you iterate through the string, if you encounter a lowercase letter, you calculate its positional index (by subtracting the ASCII value of 'a' from that of the letter) and then set the corresponding bit in mask1. Similarly, for an uppercase letter, you calculate the index (subtracting 'A') and set the corresponding bit in mask2.

After scanning all letters in the string and updating the bit masks, you compute the bitwise AND of the two masks (mask1 & mask2). This will give you a new mask that has bits set only at positions where both a lowercase and uppercase instance of that letter exists in s.

The last part is to find the highest set bit in the combined mask, which represents the greatest letter present in both forms. The bit_length method is used to find the position of the highest set bit. Since you're looking for the actual letter, not the index, you have to add the ASCII value of 'A' to convert the index back to the character. In the event where no bits are set in the combined mask, it indicates there is no such letter that meets the criteria, and an empty string should be returned.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution approach uses bit manipulation techniques to efficiently track whether each letter in the English alphabet appears as both a lowercase and uppercase in the string s.

Algorithm Steps:

Initialize two variables mask1 and mask2 to 0. Each will serve as a bitmask to track the occurrence of lowercase and uppercase letters, respectively.
Loop through each character c in the string s.
For each character c, determine if it's lowercase or uppercase.
- If it is lowercase, find the difference between the ASCII values of c and 'a'. This difference gives the index (0 for 'a', 1 for 'b', ..., 25 for 'z').
- Set the corresponding bit in mask1 by shifting 1 left by the index calculated above. This is done with mask1 |= 1 << (ord(c) - ord("a")).
If the character is uppercase, perform a similar operation as step 3 but on mask2 by finding the difference between the ASCII values of c and 'A'.
After completing the loop, use a bitwise AND operation between mask1 and mask2 to find common letters (bits set in both masks). mask = mask1 & mask2.
Find the greatest (most significant) bit set in mask. This is done using mask.bit_length(), which returns the number of bits necessary to represent mask in binary, which is also the position of the highest bit set plus one.
If mask is not zero, convert the index of the greatest bit set back to an uppercase letter using chr(mask.bit_length() - 1 + ord("A")).
If mask is zero, which means no bit is set and no such common letter in both cases exists, return an empty string.

Data Structures:

Two integer bit masks (variables mask1 and mask2) to track the presence of each lowercase and uppercase letter, efficiently using bitwise operations.

Patterns Used:

Bit Manipulation: To compactly store and compute the presence of letters and to find the greatest letter present in both forms.
ASCII Value Calculations: To map characters to their respective positions in the bitmask and vice versa.

By following this approach, the algorithm uses constant space regardless of the size of the input string and linear time in terms of the length of the string s.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the string s = "aAbBdDxXyYzZcC" and we want to find the largest letter that exists both in lowercase and uppercase in this string.

We initialize mask1 and mask2 to 0. These will track lowercase and uppercase letters, respectively.
We start looping through the string s. The first character is 'a', which is lowercase.
We calculate the index for 'a' by subtracting the ASCII value of 'a' from it (which is 0) and set the corresponding bit in mask1 (so mask1 now has the least significant bit set).
We encounter 'A', which is uppercase. We calculate its index (also 0) and set the corresponding bit in mask2.
Continuing this process, mask1 and mask2 will have bits set based on the lowercase and uppercase letters, respectively.

After processing all characters, suppose mask1 = 0011001100010101 and mask2 = 0011001100010101.
We apply a bitwise AND operation on mask1 and mask2, which gives us mask = 0011001100010101, showing that we have common letters.
We use mask.bit_length() to find the highest set bit, which in this case would return 14. This means the letter we are looking for corresponds to the bit just before the 14th position in the mask (because bit_length returns the position of the highest set bit plus one).
We subtract 1 from this value to get the actual index of the letter in the mask and add the ASCII value of 'A' to convert it back to the character, giving us 'Z', which is our answer. The calculation will look like chr(14 - 1 + ord('A')).

If no common uppercase and lowercase letter was present in s, mask would be 0 and we would return an empty string. But in this example, we found 'Z' as the largest letter that exists in both cases, so the final result is 'Z'.

Solution Implementation

1class Solution:
2    def greatestLetter(self, s: str) -> str:
3        # Initialize bit masks for lowercase and uppercase letters.
4        lowercase_mask = 0
5        uppercase_mask = 0
6      
7        # Iterate through each character in the string.
8        for char in s:
9            # If the character is lowercase,
10            # set the corresponding bit in the lowercase bit mask.
11            if char.islower():
12                lowercase_mask |= 1 << (ord(char) - ord('a'))
13            # If the character is uppercase,
14            # set the corresponding bit in the uppercase bit mask.
15            else:
16                uppercase_mask |= 1 << (ord(char) - ord('A'))
17      
18        # Calculate the intersection bit mask to find common letters in upper and lowercase.
19        common_letters_mask = lowercase_mask & uppercase_mask
20      
21        # If there are common letters, find the greatest one.
22        if common_letters_mask:
23            # Calculate the most significant bit's position and convert it back to an uppercase letter.
24            # The 'bit_length' method returns the position of the highest 1 bit,
25            # corresponding to the largest letter available in both cases.
26            greatest_letter_ascii = common_letters_mask.bit_length() - 1 + ord('A')
27            return chr(greatest_letter_ascii)
28        else:
29            # If there are no common letters, return an empty string.
30            return ""
31

1class Solution {
2    public String greatestLetter(String s) {
3        // Initialize two masks to keep track of lower and upper case letters.
4        int lowerCaseMask = 0, upperCaseMask = 0;
5      
6        // Iterate through each character in the string.
7        for (int i = 0; i < s.length(); ++i) {
8            char c = s.charAt(i);
9          
10            // If the character is a lower case letter, update the lowerCaseMask.
11            if (Character.isLowerCase(c)) {
12                lowerCaseMask |= 1 << (c - 'a');
13            }
14            // If the character is an upper case letter, update the upperCaseMask.
15            else {
16                upperCaseMask |= 1 << (c - 'A');
17            }
18        }
19      
20        // Calculate the common mask to identify letters appearing in both cases.
21        int commonMask = lowerCaseMask & upperCaseMask;
22      
23        // If there is at least one letter in commonMask, calculate and return the greatest letter.
24        if (commonMask > 0) {
25            // Find the largest index of the set bit which represents the greatest letter.
26            // '31 - Integer.numberOfLeadingZeros(commonMask)' gives the last (greatest) index where the bit is set.
27            // Adding 'A' converts it back to the ASCII character.
28            return String.valueOf((char) (31 - Integer.numberOfLeadingZeros(commonMask) + 'A'));
29        } else {
30            // If commonMask is zero, it means no letter exists in both cases, return an empty string.
31            return "";
32        }
33    }
34}
35

1class Solution {
2public:
3    // This method finds the greatest letter that appears both in lower and upper case in the input string.
4    string greatestLetter(string s) {
5        // Initialize two bitmasks to track the presence of 26 lowercase and 26 uppercase letters.
6        int lowercaseMask = 0;
7        int uppercaseMask = 0;
8
9        // Iterate through each character of the string
10        for (char &c : s) {
11            // If the character is lowercase
12            if (islower(c)) {
13                // Set the corresponding bit in the lowercase mask
14                lowercaseMask |= 1 << (c - 'a');
15            } 
16            // If the character is uppercase
17            else {
18                // Set the corresponding bit in the uppercase mask
19                uppercaseMask |= 1 << (c - 'A');
20            }
21        }
22
23        // The 'mask' will only have bits set that are common in both uppercase and lowercase masks
24        // It represents letters existing in both cases
25        int mask = lowercaseMask & uppercaseMask;
26
27        // If there is at least one common letter
28        if (mask != 0) {
29            // __builtin_clz returns the number of leading 0-bits, hence 31 - __builtin_clz(mask)
30            // Gives the position of the highest-order bit that is set to 1
31            // Then we add 'A' to get the ASCII value of the greatest letter
32            // that appears in both lower and uppercase in the string 's'.
33            return string(1, 'A' + 31 - __builtin_clz(mask));
34        } else {
35            // If there is no common letter, return an empty string
36            return "";
37        }
38    }
39};
40

1function greatestLetter(s: string): string {
2    // Initialize an array to track the occurrence of characters in the string, 
3    // sized to fit the ASCII table for uppercase and lowercase English letters.
4    const seenCharacters = new Array(128).fill(false);
5
6    // Iterate through each character in the provided string,
7    // and record its occurrence in the seenCharacters array
8    // by setting the corresponding ASCII index to true.
9    for (const char of s) {
10        seenCharacters[char.charCodeAt(0)] = true;
11    }
12
13    // Iterate backwards from ASCII code 90 (Z) to 65 (A) to find the largest lexicographical
14    // uppercase letter that has both uppercase and lowercase forms present in the string.
15    for (let i = 90; i >= 65; --i) {
16        // Check if current letter i is present in both its uppercase and lowercase forms.
17        if (seenCharacters[i] && seenCharacters[i + 32]) {
18            // If a valid letter is found, return the uppercase character as the result.
19            return String.fromCharCode(i);
20        }
21    }
22
23    // If no such letter is found, return an empty string.
24    return '';
25}
26

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the code is dominated by the loop running through every character in the input string, s. Each iteration performs a constant amount of work: bitwise operations and comparisons. As s can be of length n, the loop runs n times. Hence, the time complexity is O(n).

Space Complexity

The space complexity of the code is determined by the two integer variables mask1 and mask2. Regardless of the length of the input string, these variables occupy a constant amount of space, as they are not dependent on the input size. Thus, the space complexity is O(1) because the space used by the algorithm does not scale with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

O(1)O(log n)O(sqrt(n))O(n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2309. Greatest English Letter in Upper and Lower Case

Problem Description

Intuition

Solution Approach

Algorithm Steps:

Data Structures:

Patterns Used:

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity