Leetcode 2309: Greatest English Letter in Upper and Lower Case
Given a string s consisting of both uppercase and lowercase English letters, return the greatest letter that appears as both a lowercase and uppercase letter in the string. The returned letter should be in uppercase. If no such letter exists, return an empty string.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s containing both uppercase and lowercase English letters.
Example: s = 'aBcDeFg'
Constraints:
• 1 <= s.length <= 1000
• s consists of lowercase and uppercase English letters.
Output: Return the greatest English letter that appears as both a lowercase and uppercase letter, in uppercase form. If no such letter exists, return an empty string.
Example: For s = 'aBcDeFg', the output is 'F'.
Constraints:
• Return the greatest letter in uppercase.
Goal: The goal is to find the letter that appears both in uppercase and lowercase, and return the greatest one in uppercase.
Steps:
• Iterate through the string s and track the occurrence of each letter in both lowercase and uppercase.
• Start from the greatest possible letter ('Z') and check if both the lowercase and uppercase versions are present in the string.
• Return the first such letter found in uppercase, or an empty string if no such letter exists.
Goal: The problem constraints ensure that the string is manageable in size and contains only English letters.
Steps:
• 1 <= s.length <= 1000
• s consists of lowercase and uppercase English letters.
Assumptions:
• The input string contains only English letters and may include both uppercase and lowercase versions of letters.
• Input: s = 'aBcDeFg'
• Explanation: The letter 'F' is the greatest letter that appears as both 'f' and 'F'. The function returns 'F'.
Approach: The approach to solving this problem involves checking for the presence of each letter as both lowercase and uppercase, then returning the greatest one.
Observations:
• We need to efficiently find a letter that appears as both lowercase and uppercase.
• Starting from the largest possible letter ('Z'), we can check each letter for both cases. If found, return that letter in uppercase.
Steps:
• 1. Initialize an array or set to track the occurrence of lowercase and uppercase letters.
• 2. Traverse the string to fill the occurrences of each letter.
• 3. Start checking from 'Z' to 'A' for both lowercase and uppercase versions of the letter.
• 4. Return the first letter found as both lowercase and uppercase in uppercase form, or return an empty string if none are found.
Empty Inputs:
• Empty strings are not possible according to the constraints.
Large Inputs:
• Handle strings of length up to 1000 efficiently.
Special Values:
• If no letter appears in both uppercase and lowercase, return an empty string.
Constraints:
• Ensure that the output is the letter in uppercase if both cases are found.
string greatestLetter(string s) {
int cnt[128] = {};
for (auto ch : s)
++cnt[ch];
for (auto ch = 'Z'; ch >= 'A'; --ch)
if (cnt[ch] && cnt[ch + 'a' - 'A'])
return string(1, ch);
return "";
}
1 : Function Declaration
string greatestLetter(string s) {
Define the function `greatestLetter` that takes a string `s` as input and returns a string containing the greatest letter (uppercase) that appears both in uppercase and lowercase.
2 : Array Initialization
int cnt[128] = {};
Initialize an array `cnt` of size 128 to store the frequency of each character in the input string. The size 128 ensures that all ASCII characters are accounted for.
3 : Loop Through String
for (auto ch : s)
Iterate through each character `ch` in the input string `s`.
4 : Character Count
++cnt[ch];
Increment the corresponding count for the character `ch` in the `cnt` array.
5 : Descending Check
for (auto ch = 'Z'; ch >= 'A'; --ch)
Start a loop that checks each uppercase letter from 'Z' to 'A'. This ensures we find the greatest possible letter first.
6 : Matching Check
if (cnt[ch] && cnt[ch + 'a' - 'A'])
Check if both the uppercase character `ch` and its corresponding lowercase character `ch + 'a' - 'A'` appear in the string.
7 : Return Result
return string(1, ch);
If both uppercase and lowercase characters are found, return the uppercase letter as a string.
8 : Return Empty String
return "";
If no matching pair of uppercase and lowercase letters is found, return an empty string.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) where n is the length of the input string, as we only iterate through the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only use a constant amount of space for tracking the occurrences of each letter.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus