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 ""
Difficulty
and has an acceptance rate of about 73% (100k+ submissions).
Typical patterns to solve this problem:
- Enumeration
- Hash Table
- String
AI Disclaimer
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.
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.
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.
Code Quality
Complexity Analysis
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
Other Solutions
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 |
Videos
Similar Problems
- problem 3120: Count the Number of Special Characters I
- problem 3121: Count the Number of Special Characters II
Solved On The Same Day
- problem 455: Assign Cookies
- problem 500: Keyboard Row
- problem 575: Distribute Candies
- problem 1009: Complement of Base 10 Integer
- problem 1071: Greatest Common Divisor of Strings
- problem 1299: Replace Elements with Greatest Element on Right Side
- problem 1748: Sum of Unique Elements
- problem 1979: Find Greatest Common Divisor of Array
- problem 2148: Count Elements With Strictly Smaller and Greater Elements
- problem 216: Combination Sum III
- problem 229: Majority Element II
- problem 373: Find K Pairs with Smallest Sums
- problem 470: Implement Rand10() Using Rand7()
- problem 503: Next Greater Element II
- problem 556: Next Greater Element III
- problem 622: Design Circular Queue
- problem 1262: Greatest Sum Divisible by Three
- problem 2657: Find the Prefix Common Array of Two Arrays
- problem 2807: Insert Greatest Common Divisors in Linked List
Extra
- 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