Problem 2309

Abstract / Summary

Find the greatest English letter that appears in both upper and lower case in a given string.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 2309.py

class Solution:
    def greatestLetter(self, s: str) -> str:
        freq = { "" }
        for c in s:
            freq.add(c)

        for c in range(25, -1, -1):
            high = chr(ord('A') + c)
            low  = chr(ord('a') + c)
            if high in freq and low in freq:
                return high

        return ""
13 lines | 343 bytes | submitted August 14, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 73% (100k+ submissions).

Typical patterns to solve this problem:
  • Enumeration
  • Hash Table
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a single method greatestLetter. The method receives a string s and returns the greatest alphabetical letter that appears in both uppercase and lowercase forms within the input. If no such letter exists, an empty string is returned. The algorithm builds a collection of unique characters from the input, then iterates from the highest letter 'Z' down to 'A', checking for the presence of each letter in both cases.

Key Steps

The first significant operation creates a set to store distinct characters encountered in the input string.

freq = { "" }
for c in s:
    freq.add(c)

Here freq is initialized with an empty string element, and each character from s is added, guaranteeing O(1) average insertion time per character.

The second major operation iterates over the alphabet in reverse order, constructing the uppercase and lowercase representation of each letter and testing their membership in the set.

for c in range(25, -1, -1):
    high = chr(ord('A') + c)
    low  = chr(ord('a') + c)
    if high in freq and low in freq:
        return high

The loop variable c runs from 25 down to 0, corresponding to letters 'Z' through 'A'. For each iteration, high holds the uppercase character and low holds the matching lowercase character. The conditional checks whether both forms are present in freq. When the condition is satisfied, the uppercase version is immediately returned as the result.

If the loop completes without finding a matching pair, the method falls back to returning an empty string.

return ""

Edge Cases Handled

The algorithm gracefully handles an empty input string. In that scenario, the set freq will contain only the initial empty string element, and the reverse alphabet loop will find no matching uppercase-lowercase pair, leading to the final empty string return.

When the input contains only one case of a particular letter (e.g., only 'a' but not 'A'), the membership test fails because both high and low must be present. This ensures that the method does not incorrectly return a letter that lacks a counterpart in the opposite case.

The presence of duplicate characters in the input does not affect correctness. Since a set automatically discards duplicates, the membership checks remain accurate regardless of how many times a character appears.

If the input includes non-alphabetic characters, they are added to the set but never considered during the reverse alphabet iteration, because the loop only generates characters within 'A'-'Z' and 'a'-'z'. Consequently, such characters are ignored without causing errors.

Performance Optimizations

The use of a set for freq provides constant-time average complexity for both insertion and membership queries. This choice eliminates the need for scanning the input string multiple times and avoids linear searches for each letter.

Iterating the alphabet in reverse order allows the method to stop at the first qualifying letter, which is the greatest one by definition. This early exit prevents unnecessary checks for lower letters once a valid pair is found.

By constructing the uppercase and lowercase characters with arithmetic on their Unicode code points (ord and chr), the code avoids costly string operations or lookups in external data structures. The arithmetic approach is lightweight and leverages the contiguous ordering of alphabetic characters in the Unicode table.

Overall, the combination of a set for fast lookups and a reverse traversal that halts on the first match yields an efficient solution for the problem at hand.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a big box filled with lots of colorful blocks that have letters on them. Some blocks are capital letters, like a big A, and some are lowercase letters, like a little a. The goal is to find the biggest letter that has both its big version and its little version inside the box.

First, the code goes through all the blocks one by one to see which letters are hiding inside. It keeps a special list of all the different letters that were found.

Next, it starts looking at the alphabet starting from the very end with the letter Z and works its way backward toward A. For every letter it checks, it looks to see if both the big version and the little version are in the list. It starts at the back because it wants to find the biggest letter first.

As soon as it finds a letter where both the big and little versions are sitting in the list, it holds that big letter up to show it found the winner. If it checks every single letter all the way down to A and still cannot find a matching pair where both versions are present, it just puts away the empty box and finishes.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 5.44 | σ = 2.02

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster Java Python C++ TS
WalkCCC Java Python C++
leetcode.ca Java Python JS C++ Go Rust TS
Progiez Java Python C++
github charles-wangkai Java
fartem Ruby
fsq C++
JoshCrozier JS
lkwq007 Python
varunu28 Java
yuanliu666 Kotlin
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez C++, Java, Python
charles-wangkai Java
fartem Ruby
fsq C++
JoshCrozier JavaScript
lkwq007 Python
varunu28 Java
yuanliu666 Kotlin
24 links | 11 authors | 9 languages

Videos

6 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

2 similar problems

Solved On The Same Day

20 solutions   August 14, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality