algoadvance

Leetcode 2309. Greatest English Letter in Upper and Lower Case

Problem Statement

Given a string s of English letters, 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.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the input string s?
   • Can the input string contain non-alphabetical characters?
2. Output Expectations:
   • If there are multiple valid letters, should the output be the greatest letter in alphabetical order?

In the absence of explicit constraints or additional clarifications, we assume:

1. The input string s contains only English alphabetical letters.
2. The maximum length of the input string s follows typical constraints you might find on competitive programming platforms, say up to (10^5) characters.

Strategy

To solve this problem, we can break it down into the following steps:

1. Set up structures to track letter occurrences: We need two sets, one for lowercase letters and one for uppercase letters.
2. Process the input string: Iterate over each character in the string and add it to the respective set based on whether it is an uppercase or lowercase letter.
3. Find the greatest common letter in both cases:
   • Iterate over the English alphabet from ‘Z’ to ‘A’.
   • For each letter, check if both its lowercase and uppercase versions are present in their respective sets.
   • Return the first letter for which this condition holds.

Code

#include <iostream>
#include <unordered_set>
#include <string>

std::string greatestEnglishLetter(std::string s) {
    std::unordered_set<char> lowercase_letters;
    std::unordered_set<char> uppercase_letters;

    // Populate the lowercase and uppercase sets
    for (auto ch : s) {
        if (islower(ch))
            lowercase_letters.insert(ch);
        if (isupper(ch))
            uppercase_letters.insert(ch);
    }
    
    // Check from 'Z' to 'A' for the greatest letter that appears in both cases
    for (char ch = 'Z'; ch >= 'A'; --ch) {
        if (lowercase_letters.count(tolower(ch)) && uppercase_letters.count(ch)) {
            return std::string(1, ch);
        }
    }
    
    // Return empty string if no such letter exists
    return "";
}

// Example usage
int main() {
    std::string s = "lEeTcOdE";
    std::cout << "Greatest English Letter: " << greatestEnglishLetter(s) << std::endl;  // Output: "E"
    return 0;
}

Time Complexity

• Space Complexity: O(1). This is because the sets lowercase_letters and uppercase_letters can at most store 26 unique characters each, regardless of the input size.
• Time Complexity: O(N + 26), where N is the length of the input string. We iterate through the string once (O(N)) and then iterate over a fixed number of letters (26) to find the required greatest English letter. Thus, the overall complexity is O(N).

This solution is efficient given the constraints and should work well for large input sizes.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?