Solution Explanation and Code for Finding the Second Largest Digit in a String

This problem asks us to find the second largest digit in a given alphanumeric string. The solution involves iterating through the string, identifying digits, and tracking the largest and second largest digits encountered.

Approach 1: One-Pass Iteration

This approach efficiently solves the problem in a single pass through the string. We maintain two variables, largest and secondLargest, initialized to -1. As we iterate:

1. Digit Check: We check if the current character is a digit using isdigit() (or equivalent function in other languages).
2. Update largest and secondLargest: If it's a digit:
   • If the digit is greater than largest, we update secondLargest to the previous largest value and largest to the current digit.
   • If the digit is smaller than largest but greater than secondLargest, we update secondLargest to the current digit.

Finally, we return secondLargest.

Time Complexity: O(n), where n is the length of the string, as we iterate through the string once. Space Complexity: O(1), as we only use a constant amount of extra space to store largest and secondLargest.

Code (Multiple Languages):

Python:

class Solution:
    def secondHighest(self, s: str) -> int:
        largest = -1
        secondLargest = -1
        for char in s:
            if char.isdigit():
                digit = int(char)
                if digit > largest:
                    secondLargest = largest
                    largest = digit
                elif digit > secondLargest and digit < largest:
                    secondLargest = digit
        return secondLargest

Java:

class Solution {
    public int secondHighest(String s) {
        int largest = -1;
        int secondLargest = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int digit = c - '0';
                if (digit > largest) {
                    secondLargest = largest;
                    largest = digit;
                } else if (digit > secondLargest && digit < largest) {
                    secondLargest = digit;
                }
            }
        }
        return secondLargest;
    }
}

C++:

class Solution {
public:
    int secondHighest(string s) {
        int largest = -1;
        int secondLargest = -1;
        for (char c : s) {
            if (isdigit(c)) {
                int digit = c - '0';
                if (digit > largest) {
                    secondLargest = largest;
                    largest = digit;
                } else if (digit > secondLargest && digit < largest) {
                    secondLargest = digit;
                }
            }
        }
        return secondLargest;
    }
};

(Other languages like JavaScript, Go, etc., can be implemented similarly following the same logic.)

Approach 2: Using a Set (Less Efficient)

This approach uses a set to store unique digits found in the string. After creating the set, we sort it in descending order and return the second element if it exists; otherwise, return -1. This approach is less efficient than the one-pass method because of the sorting step.

Time Complexity: O(n log n) due to sorting the set (where n is the number of unique digits). Space Complexity: O(n) in the worst case to store the set of unique digits.

This approach is less optimal than Approach 1 because of its higher time complexity. Approach 1 provides a more efficient solution for this problem.