Teaching Kids Programming – Greatest English Letter in Upper and Lower Case

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Hints:
Consider iterating through the string and storing each unique character that occurs in a set.
From Z to A, check whether both the uppercase and lowercase version occur in the set.

Greatest English Letter in Upper and Lower Case

The bruteforce algorithm works perfectly fine. We can iterate backwards the alphabet letters from Z to A and return the first uppercase letter when the two cases appear in the string. The ASCII for ‘A’ is 65 and ‘a’ is 97.

To convert to string to set costs O(N) time and O(N) space – but we achieve O(1) character in set check. Overall time complexity is O(N) – as the checking takes 26 iterations that should be considered as O(1).

1
2
3
4
5
6
7
8
9

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)
        for i in range(25, -1, -1):
            ch1 = chr(97 + i)
            ch2 = chr(65 + i)
            if ch1 in s and ch2 in s:
                return ch2
        return ""

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)
        for i in range(25, -1, -1):
            ch1 = chr(97 + i)
            ch2 = chr(65 + i)
            if ch1 in s and ch2 in s:
                return ch2
        return ""

We can use predefined alphabeta uppercase aka ascii_uppercase to simplify the algorithm without using the magic numbers 97 or 65.

1
2
3
4
5
6
7

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)
        for i in ascii_uppercase[::-1]:
            if i in s and i.lower() in s:
                return i
        return ""

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)
        for i in ascii_uppercase[::-1]:
            if i in s and i.lower() in s:
                return i
        return ""

Another solution is to sort the unique letters, and check if both cases appear by using the swapcase. ‘A’.swapcase() is ‘a’ while ‘a’.swapcase() is ‘A’. Sorting takes O(NLogN) time.

1
2
3
4
5
6
7

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)
        for i in sorted(s, reverse=True):
            if i.swapcase() in s:
                return i.upper()
        return "" 

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)
        for i in sorted(s, reverse=True):
            if i.swapcase() in s:
                return i.upper()
        return "" 

We can also solve this via set intersection. We can find the letters that appear in both uppercase and lowercases via set intersection of two sets: uppercase letters, and uppercase letters that are transformed from existing lowercase letters. Then we need to sort the common part and return the greatest.

1
2
3
4
5
6
7

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)        
        uppers = {x for x in s if x.isupper()}
        lowers = {x.upper() for x in s if x.islower()}
        both = uppers & lowers
        return sorted(both, reverse = True)[0] if both else ""

class Solution:
    def greatestLetter(self, s: str) -> str:
        s = set(s)        
        uppers = {x for x in s if x.isupper()}
        lowers = {x.upper() for x in s if x.islower()}
        both = uppers & lowers
        return sorted(both, reverse = True)[0] if both else ""

In worst cases, the time complexity is O(NLogN) because of sorting.

–EOF (The Ultimate Computing & Technology Blog) —