2309. Greatest English Letter in Upper and Lower Case
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.
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
andmask2
to0
. Each will serve as a bitmask to track the occurrence of lowercase and uppercase letters, respectively. -
Loop through each character
c
in the strings
. -
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 shifting1
left by the index calculated above. This is done withmask1 |= 1 << (ord(c) - ord("a"))
.
- If it is lowercase, find the difference between the ASCII values of
-
If the character is uppercase, perform a similar operation as step 3 but on
mask2
by finding the difference between the ASCII values ofc
and'A'
. -
After completing the loop, use a bitwise AND operation between
mask1
andmask2
to find common letters (bits set in both masks).mask = mask1 & mask2
. -
Find the greatest (most significant) bit set in
mask
. This is done usingmask.bit_length()
, which returns the number of bits necessary to representmask
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 usingchr(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
andmask2
) 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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
andmask2
to0
. 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 inmask1
(somask1
now has the least significant bit set). -
We encounter
'A'
, which is uppercase. We calculate its index (also 0) and set the corresponding bit inmask2
. -
Continuing this process,
mask1
andmask2
will have bits set based on the lowercase and uppercase letters, respectively.After processing all characters, suppose
mask1 = 0011001100010101
andmask2 = 0011001100010101
. -
We apply a bitwise AND operation on
mask1
andmask2
, which gives usmask = 0011001100010101
, showing that we have common letters. -
We use
mask.bit_length()
to find the highest set bit, which in this case would return14
. This means the letter we are looking for corresponds to the bit just before the 14th position in the mask (becausebit_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 likechr(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
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.
In a binary min heap, the maximum element can be found in:
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!