algoadvance

Leetcode 1796. Second Largest Digit in a String

Problem Statement

You are given a string s which consists of only digits and lowercase English letters. Your task is to return the second largest digit in the string. If there is no such digit, return -1.

Clarifying Questions

  1. What is the expected length of the input string?
    • This helps determine if the algorithm needs optimization for very long strings.
  2. Are there any special characters or other types in the string?
    • According to the problem statement, the string consists only of digits and lowercase English letters.
  3. How should we handle an empty string, or a string that has no digits?
    • The problem specifies that if there is no second largest digit, we should return -1.

Strategy

  1. Filter and Collect Digits:
    • Iterate through the string and collect all the digit characters.
  2. Find Unique Digits:
    • Insert these digits into a set to automatically handle duplicates and keep unique digits.
  3. Sort and Identify:
    • Convert the set to a list and sort it in descending order. The second largest element, if it exists, will be the second element of the sorted list (index 1).
  4. Edge Cases:
    • If there is only one unique digit or no digits in the string, return -1.

Code

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>

int secondHighest(const std::string& s) {
    std::set<int> digitSet;
    
    // Step 1: Collect digits from the string
    for(char ch : s) {
        if(isdigit(ch)) {
            digitSet.insert(ch - '0'); // Convert char digit to int and insert into set
        }
    }
    
    // Step 2: Check if we have enough unique digits
    if(digitSet.size() < 2) {
        return -1;
    }
    
    // Step 3: Find the second largest unique digit
    std::vector<int> digits(digitSet.begin(), digitSet.end());
    std::sort(digits.rbegin(), digits.rend()); // Sort in descending order
    
    return digits[1]; // Return the second largest digit
}

int main() {
    // Test cases
    std::string test1 = "dfa12321afd";
    std::cout << "Second largest digit in \"" << test1 << "\": " << secondHighest(test1) << std::endl;
    
    std::string test2 = "abc1111";
    std::cout << "Second largest digit in \"" << test2 << "\": " << secondHighest(test2) << std::endl;
    
    std::string test3 = "a5b6c7";
    std::cout << "Second largest digit in \"" << test3 << "\": " << secondHighest(test3) << std::endl;

    return 0;
}

Time Complexity

Therefore, the time complexity for this approach is O(n), where n is the length of the string. The space complexity is O(1) because the set of unique digits is at most size 10.

Feel free to ask if you need further clarifications or have additional requirements!

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