Greatest English Letter In Upper And Lower Case - Leetcode Solution

Problem Statement:

Given a string S, find the largest alphabetical character, whose both uppercase and lowercase appear in S. The uppercase character should be returned. For example, for S = "admeDCAB", the answer is "D".

Solution:

The problem asks us to find the highest alphabetical character, whose both uppercase and lowercase versions are present in the given string. In other words, we need to find the letter that is present in both uppercase and lowercase in S, and is also the highest in the alphabetical order.

We can solve this problem using the following steps:

Step 1: Initialize max_char to None and create a set s to keep track of all the lowercase letters in the string.

Step 2: Iterate over the characters in the string. If the current character is uppercase and its lowercase version is in s, then check if it is greater than max_char. If it is greater than max_char, update max_char.

Step 3: If we have found a character that satisfies the conditions, return max_char. Otherwise, return "NO".

Here's the Python code for the solution:

def highest_letter(s): max_char = None lower_set = set(c.lower() for c in s)

for c in s:
    if c.isupper() and c.lower() in lower_set:
        if not max_char or c > max_char:
            max_char = c

if max_char:
    return max_char
else:
    return "NO"

Time Complexity:

The time complexity of the above solution is O(n) where n is the length of the input string S. This is because we are iterating over each character of the string only once.

Space Complexity:

The space complexity of the above solution is O(k) where k is the number of distinct lowercase characters in S. This is because we are using a set to store the distinct lowercase characters present in the input string S. In the worst case, when all the characters in S are lowercase and distinct, the size of the set will be equal to the length of S.

Overall, the code provides an efficient solution to the problem and can be run within the given constraints.

1