Code Implementation

class Solution:
    def secondHighest(self, s: str) -> int:
        digits = set()
        for ch in s:
            if ch.isdigit():
                digits.add(int(ch))
        if len(digits) < 2:
            return -1
        return sorted(digits, reverse=True)[1]
      

class Solution {
public:
    int secondHighest(string s) {
        set<int> digits;
        for (char ch : s) {
            if (isdigit(ch)) {
                digits.insert(ch - '0');
            }
        }
        if (digits.size() < 2) return -1;
        auto it = digits.rbegin();
        ++it;
        return *it;
    }
};
      

class Solution {
    public int secondHighest(String s) {
        Set<Integer> digits = new HashSet<>();
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                digits.add(ch - '0');
            }
        }
        if (digits.size() < 2) return -1;
        List<Integer> list = new ArrayList<>(digits);
        Collections.sort(list, Collections.reverseOrder());
        return list.get(1);
    }
}
      

var secondHighest = function(s) {
    let digits = new Set();
    for (let ch of s) {
        if (ch >= '0' && ch <= '9') {
            digits.add(Number(ch));
        }
    }
    if (digits.size < 2) return -1;
    let arr = Array.from(digits).sort((a, b) => b - a);
    return arr[1];
};
      

Problem Description

Given a string s that consists of lowercase English letters and digits, your task is to return the second largest numerical digit that appears in s. If there is no such digit, return -1.

• Only numerical digits ('0' to '9') are considered.
• Each digit is considered only once, even if it appears multiple times.
• If there is only one unique digit or none, return -1.

Thought Process

The problem asks us to find the second largest digit in a string. At first glance, we might think about scanning the string, collecting the digits, and then somehow figuring out which is the second largest. A brute-force approach could involve storing all digits, sorting them, and picking the second largest. But we can do better by using a set to avoid duplicates and only keeping track of unique digits. This reduces unnecessary work and makes our solution more efficient.

The key insight is to recognize that we only care about unique digits, and their order from largest to smallest. We don't need to store the entire string or worry about letter characters at all.

Solution Approach

Here is a step-by-step guide to solving the problem efficiently:

1. Initialize a Set: We use a set to collect unique digits. This ensures that repeated digits are only counted once and lookup/insertions are fast.
2. Iterate through the String: For each character in s, check if it's a digit. If so, convert it to an integer and add it to the set.
3. Check if Enough Digits Exist: After processing the string, if the set has fewer than two elements, return -1 because there is no second largest digit.
4. Find the Second Largest: Otherwise, sort the set in descending order and pick the second element.

This approach is efficient because:

• Sets automatically handle duplicates.
• We only need to sort at most 10 elements (the possible digits).
• We avoid unnecessary storage and operations on non-digit characters.

Example Walkthrough

Let's work through an example with s = "dfa12321afd":

1. We scan each character:
   • 'd', 'f', 'a' - not digits, skip.
   • '1' - digit, add 1 to set.
   • '2' - digit, add 2 to set.
   • '3' - digit, add 3 to set.
   • '2' - digit, already in set, ignore.
   • '1' - digit, already in set, ignore.
   • 'a', 'f', 'd' - not digits, skip.
2. Set now contains: {1, 2, 3}
3. Sort in descending order: [3, 2, 1]
4. The second largest is 2. Return 2.

If the input was "abc1111", the set would be {1}, so we return -1.

Time and Space Complexity

• Brute-force approach: Collect all digits, sort them (O(n log n)), and remove duplicates (O(n)). This is less efficient, especially with longer strings.
• Optimized approach (using a set):
  • Time Complexity: O(n), where n is the length of the string (for scanning). Sorting the set is O(1) since there are at most 10 digits.
  • Space Complexity: O(1), because the set can never have more than 10 elements (digits 0-9).

Summary

To solve the "Second Largest Digit in a String" problem, we scan the string and collect unique digits using a set. After ensuring there are at least two unique digits, we sort them and return the second largest. This approach is efficient, simple, and leverages the properties of sets and the limited range of digits, making it both elegant and practical for this task.