Jobs

Interviews

Discussions

Greatest English Letter in Upper and Lower Case

Easy

Asked by:

7 views

Topics:

Strings

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.

Try coding it in LeetCode

Greatest English Letter in Upper and Lower Case

Easy

Asked by:

7 views

Topics:

Strings

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`?
Is the input string guaranteed to contain only English letters (a-z, A-Z)?
If multiple English letters exist in both upper and lowercase, should I return the largest in alphabetical order (Z being the largest)?
What should I return if the input string is empty?
Is the problem case-sensitive (e.g., should I consider 'a' and 'A' as the same character)?

Brute Force Solution

Approach

The brute force method for this problem means we're going to check every single letter of the alphabet. We'll look to see if both its uppercase and lowercase versions appear in the input. We will remember the greatest letter that satisfies this requirement.

Here's how the algorithm would work step-by-step:

Start with the letter 'Z'.
Check if both 'Z' and 'z' are present in the input.
If they are, remember 'Z' and stop checking, because it's the greatest letter that works.
If they are not, move to the next letter, 'Y'.
Check if both 'Y' and 'y' are present in the input.
If they are, remember 'Y' and stop checking.
If they are not, keep going to the previous letter.
Continue this process, going through 'X', 'W', 'V', and so on, all the way down to 'A'.
If you find a letter that satisfies the condition (both uppercase and lowercase versions are present), immediately stop and that's your answer.
If you get all the way to 'A' and you haven't found a letter that works, then there isn't any letter that appears in both uppercase and lowercase, so the answer is nothing.

Code Implementation

def greatest_letter(input_string: str) -> str:
    for char_code in range(ord('Z'), ord('A') - 1, -1):
        uppercase_letter = chr(char_code)
        lowercase_letter = chr(char_code + 32)

        # Check for both cases of the letter.
        if uppercase_letter in input_string and lowercase_letter in input_string:
            return uppercase_letter

        # If we reach here, the current letter is not the answer.

    # No matching letter found.
    return ""

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the English alphabet from 'Z' to 'A' a maximum of 26 times, which is a constant. For each letter, it checks if both its uppercase and lowercase versions are present in the input string. This presence check involves iterating through the input string of length n. Therefore, the dominant operation is scanning the input string a constant number of times (at most 26), making the overall time complexity O(n).

Space Complexity

O(1) – The provided algorithm iterates through the English alphabet from 'Z' to 'A', checking for the presence of uppercase and lowercase letters within the input string. It only needs to store a single variable to remember the greatest letter that satisfies the condition. No additional data structures that scale with the input string's size (N, which is the length of the input string) are used, meaning that the extra space remains constant regardless of the input size. Therefore, the space complexity is O(1).

Optimal Solution

Approach

To find the greatest English letter appearing in both upper and lower case, we want to efficiently check for pairs. Instead of looking at every letter, we'll use a trick to quickly see if a letter appears as both uppercase and lowercase.

Here's how the algorithm would work step-by-step:

First, keep track of all the uppercase and lowercase letters that appear in the input.
Then, start checking the letters from Z down to A.
For each letter, see if both the uppercase version and the lowercase version are present in your saved letters.
If you find a letter where both versions exist, that's your answer – it's the greatest one that appears in both forms. Stop looking once you find it.
If you go through all the letters from Z to A and don't find a match, then no such letter exists.

Code Implementation

def greatest_letter(input_string):
    for char_code in range(ord('Z'), ord('A') - 1, -1):
        uppercase_letter = chr(char_code)
        lowercase_letter = chr(char_code + 32)

        # Check if both upper and lowercase exist
        if uppercase_letter in input_string and lowercase_letter in input_string:

            # Return the greatest letter found
            return uppercase_letter

    # No matching letter found
    return ""

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by two main steps. First, iterating through the input string of length n to record the presence of uppercase and lowercase letters, which takes O(n) time. Second, iterating from 'Z' to 'A' (a fixed number of 26 iterations, i.e., constant time), and for each letter, performing a constant-time lookup to check if both cases exist. Since the lookup is constant time and the Z to A loop is constant, the overall time complexity is dominated by the initial O(n) pass through the input string. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The algorithm tracks uppercase and lowercase letters using two data structures which can be implemented as sets or arrays. Since the English alphabet has a fixed size of 26 letters, the maximum space required for each of these data structures is constant, independent of the input string's length. Therefore, the auxiliary space used is constant, regardless of the input size N. The space used remains constant as the maximum number of uppercase and lowercase English letters will never exceed 26, simplifying to O(1).

Edge Cases

Case	How to Handle
Empty input string	Return an empty string as there are no characters to evaluate.
Input string contains non-alphabetic characters	Filter out non-alphabetic characters or raise an exception to maintain expected input format.
Input string contains only uppercase letters	Return an empty string as no lowercase versions exist.
Input string contains only lowercase letters	Return an empty string as no uppercase versions exist.
Input string contains mixed-case letters, but no pair exists	Return an empty string as no valid solution exists.
Input string contains multiple valid letter pairs; find the largest	Iterate and keep track of the largest character found so far.
Input string contains only one character	Return an empty string because to qualify, the string needs to contain both upper and lower case of the same character.
Very long input string exceeding memory or causing performance issues	Use a memory efficient approach, like using a set to store the characters to prevent scalability issues.

Empty input string

How to Handle:

Return an empty string as there are no characters to evaluate.

Input string contains non-alphabetic characters

How to Handle:

Filter out non-alphabetic characters or raise an exception to maintain expected input format.

Input string contains only uppercase letters

How to Handle:

Return an empty string as no lowercase versions exist.

Input string contains only lowercase letters

How to Handle:

Return an empty string as no uppercase versions exist.

Input string contains mixed-case letters, but no pair exists

How to Handle:

Return an empty string as no valid solution exists.

Input string contains multiple valid letter pairs; find the largest

How to Handle:

Iterate and keep track of the largest character found so far.

Input string contains only one character

How to Handle:

Return an empty string because to qualify, the string needs to contain both upper and lower case of the same character.

Very long input string exceeding memory or causing performance issues

How to Handle:

Use a memory efficient approach, like using a set to store the characters to prevent scalability issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum length of the input string `s`?
Is the input string guaranteed to contain only English letters (a-z, A-Z)?
If multiple English letters exist in both upper and lowercase, should I return the largest in alphabetical order (Z being the largest)?
What should I return if the input string is empty?
Is the problem case-sensitive (e.g., should I consider 'a' and 'A' as the same character)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the letter 'Z'.
Check if both 'Z' and 'z' are present in the input.
If they are, remember 'Z' and stop checking, because it's the greatest letter that works.
If they are not, move to the next letter, 'Y'.
Check if both 'Y' and 'y' are present in the input.
If they are, remember 'Y' and stop checking.
If they are not, keep going to the previous letter.
Continue this process, going through 'X', 'W', 'V', and so on, all the way down to 'A'.
If you find a letter that satisfies the condition (both uppercase and lowercase versions are present), immediately stop and that's your answer.
If you get all the way to 'A' and you haven't found a letter that works, then there isn't any letter that appears in both uppercase and lowercase, so the answer is nothing.

Code Implementation

def greatest_letter(input_string: str) -> str:
    for char_code in range(ord('Z'), ord('A') - 1, -1):
        uppercase_letter = chr(char_code)
        lowercase_letter = chr(char_code + 32)

        # Check for both cases of the letter.
        if uppercase_letter in input_string and lowercase_letter in input_string:
            return uppercase_letter

        # If we reach here, the current letter is not the answer.

    # No matching letter found.
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, keep track of all the uppercase and lowercase letters that appear in the input.
Then, start checking the letters from Z down to A.
For each letter, see if both the uppercase version and the lowercase version are present in your saved letters.
If you find a letter where both versions exist, that's your answer – it's the greatest one that appears in both forms. Stop looking once you find it.
If you go through all the letters from Z to A and don't find a match, then no such letter exists.

Code Implementation

def greatest_letter(input_string):
    for char_code in range(ord('Z'), ord('A') - 1, -1):
        uppercase_letter = chr(char_code)
        lowercase_letter = chr(char_code + 32)

        # Check if both upper and lowercase exist
        if uppercase_letter in input_string and lowercase_letter in input_string:

            # Return the greatest letter found
            return uppercase_letter

    # No matching letter found
    return ""

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string	Return an empty string as there are no characters to evaluate.
Input string contains non-alphabetic characters	Filter out non-alphabetic characters or raise an exception to maintain expected input format.
Input string contains only uppercase letters	Return an empty string as no lowercase versions exist.
Input string contains only lowercase letters	Return an empty string as no uppercase versions exist.
Input string contains mixed-case letters, but no pair exists	Return an empty string as no valid solution exists.
Input string contains multiple valid letter pairs; find the largest	Iterate and keep track of the largest character found so far.
Input string contains only one character	Return an empty string because to qualify, the string needs to contain both upper and lower case of the same character.
Very long input string exceeding memory or causing performance issues	Use a memory efficient approach, like using a set to store the characters to prevent scalability issues.

Empty input string

How to Handle:

Return an empty string as there are no characters to evaluate.

Input string contains non-alphabetic characters

How to Handle:

Filter out non-alphabetic characters or raise an exception to maintain expected input format.

Input string contains only uppercase letters

How to Handle:

Return an empty string as no lowercase versions exist.

Input string contains only lowercase letters

How to Handle:

Return an empty string as no uppercase versions exist.

Input string contains mixed-case letters, but no pair exists

How to Handle:

Return an empty string as no valid solution exists.

Input string contains multiple valid letter pairs; find the largest

How to Handle:

Iterate and keep track of the largest character found so far.

Input string contains only one character

How to Handle:

Return an empty string because to qualify, the string needs to contain both upper and lower case of the same character.

Very long input string exceeding memory or causing performance issues

How to Handle:

Use a memory efficient approach, like using a set to store the characters to prevent scalability issues.