Introduction

In this blog post, we will explore how to solve the LeetCode problem "2309" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

Here's a breakdown of the solution and the code:

• High-Level Approach:

  • Use sets to efficiently track lowercase and uppercase letters present in the string.
  • Iterate through the alphabet in reverse order (from 'Z' to 'A') to find the greatest letter present in both sets.
  • Return the uppercase letter if found, otherwise return an empty string.

• Complexity:

  • Runtime Complexity: O(n) where n is the length of the string s. The iteration through the string is O(n) and the constant-time set operations are performed on each character. The iteration through the alphabet ('Z' to 'A') is O(1) as it's a fixed number of iterations (26).
  • Storage Complexity: O(1). The lowercase and uppercase sets can hold at most 26 characters each (all letters of the alphabet), making it constant space.

Code

    def greatestLetter(s: str) -> str:
    """
    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.
    """
    lowercase = set()
    uppercase = set()

    for char in s:
        if 'a' <= char <= 'z':
            lowercase.add(char)
        else:
            uppercase.add(char)

    for char_code in range(ord('Z'), ord('A') - 1, -1):
        char = chr(char_code)
        if char.lower() in lowercase and char in uppercase:
            return char

    return ""