Problem Description

You are given an alphanumeric string s that contains lowercase English letters and digits. Your task is to find the second largest numerical digit that appears in the string.

The problem asks you to:

• Scan through the string and identify all digit characters (0-9)
• Find the second largest unique digit among them
• Return this second largest digit as an integer
• If there is no second largest digit (for example, if the string has no digits, only one unique digit, or all digits are the same), return -1

For example:

• If s = "abc123", the digits are 1, 2, 3. The largest is 3 and the second largest is 2, so return 2
• If s = "abc111", there's only one unique digit (1), so return -1
• If s = "abc", there are no digits, so return -1

The solution uses two variables a and b to track the largest and second largest digits respectively. As it iterates through the string:

• When a digit larger than the current largest is found, the previous largest becomes the second largest
• When a digit between the second largest and largest is found, it updates the second largest
• This ensures we always maintain the top two unique digit values

Intuition

To find the second largest digit, we need to keep track of the top two distinct digits we've seen so far. Think of it like maintaining a leaderboard with only two positions - first place and second place.

The key insight is that we don't need to collect all digits first and then sort them. Instead, we can maintain just two variables as we scan through the string once. This is similar to finding the maximum element in an array, but extended to track the top two elements.

As we encounter each digit character, there are three possible scenarios:

1. The digit is larger than our current largest - in this case, our current largest gets "bumped down" to become the second largest, and this new digit becomes the largest
2. The digit is between our second largest and largest - it becomes our new second largest
3. The digit is smaller than or equal to our second largest - we ignore it as it doesn't affect our top two

The elegant part of this approach is the update logic: when we find a new maximum with v > a, we can update both values in one go with a, b = v, a. This simultaneously promotes the old maximum to second place and installs the new maximum.

We initialize both tracking variables to -1 because this serves as both a sentinel value (indicating "no digit found yet") and conveniently matches our required return value when no second largest exists. This eliminates the need for special case handling at the end.

Solution Approach

We implement a one-pass algorithm that scans through the string once while maintaining two variables to track the largest and second largest digits.

Initialization:

• Set a = -1 to track the largest digit found
• Set b = -1 to track the second largest digit found
• Using -1 as initial values since it's both our "not found" indicator and the required return value when no second largest exists

Main Loop: For each character c in the string s:

1. Check if c is a digit using c.isdigit()
2. If it's a digit, convert it to integer v = int(c)
3. Apply the update logic:
   • Case 1: If v > a (found a new maximum):
     • Update both values: a, b = v, a
     • This moves the old largest to second place and installs the new largest
   • Case 2: If b < v < a (found a value between second and first):
     • Update only the second largest: b = v
     • This improves our second largest without affecting the first
   • Case 3: If v <= b or v == a:
     • Do nothing, as this digit doesn't improve our top two

Return Result: After traversing the entire string, return b which contains:

• The second largest digit if it exists
• -1 if no second largest digit was found

The algorithm handles edge cases naturally:

• If the string has no digits, both a and b remain -1
• If only one unique digit exists, b remains -1
• Duplicate digits are handled correctly since we use strict inequality checks

Time Complexity: O(n) where n is the length of the string - we traverse it once Space Complexity: O(1) - we only use two variables regardless of input size

Example Walkthrough

Let's trace through the example s = "dfa12321afd" to see how our algorithm finds the second largest digit.

Initial State:

• a = -1 (largest digit)
• b = -1 (second largest digit)

Step-by-step iteration:

1. c = 'd': Not a digit, skip. State: a = -1, b = -1

2. c = 'f': Not a digit, skip. State: a = -1, b = -1

3. c = 'a': Not a digit, skip. State: a = -1, b = -1

4. c = '1': Is a digit! v = 1

   • Check: v > a? → 1 > -1? Yes!
   • Update: a, b = 1, -1
   • State: a = 1, b = -1

5. c = '2': Is a digit! v = 2

   • Check: v > a? → 2 > 1? Yes!
   • Update: a, b = 2, 1
   • State: a = 2, b = 1

6. c = '3': Is a digit! v = 3

   • Check: v > a? → 3 > 2? Yes!
   • Update: a, b = 3, 2
   • State: a = 3, b = 2

7. c = '2': Is a digit! v = 2

   • Check: v > a? → 2 > 3? No
   • Check: b < v < a? → 2 < 2 < 3? No (v equals b)
   • No update needed
   • State: a = 3, b = 2

8. c = '1': Is a digit! v = 1

   • Check: v > a? → 1 > 3? No
   • Check: b < v < a? → 2 < 1 < 3? No
   • No update needed
   • State: a = 3, b = 2

9. c = 'a': Not a digit, skip. State: a = 3, b = 2

10. c = 'f': Not a digit, skip. State: a = 3, b = 2

11. c = 'd': Not a digit, skip. State: a = 3, b = 2

Final Result: Return b = 2

The algorithm correctly identifies that among the digits {1, 2, 3}, the second largest is 2. Notice how when we encountered the digit '2' again in step 7, we didn't update our variables since it was already tracked as our second largest.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because the algorithm iterates through each character in the string exactly once using a single for loop. Each operation inside the loop (checking if a character is a digit, converting to integer, and comparing/updating variables) takes constant time O(1).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size - specifically two integer variables a and b to track the highest and second-highest digits, and a temporary variable v to store the current digit value. The space usage does not grow with the size of the input string.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Duplicate Digits Correctly

The Problem: A common mistake is updating the second highest when encountering a digit equal to the current highest. This leads to incorrect results when the largest digit appears multiple times.

Incorrect Implementation:

if digit_value >= highest:  # Wrong: using >= instead of >
    second_highest = highest
    highest = digit_value

Example Where It Fails:

• Input: "abc9d9ef2"
• Expected output: 2 (digits are 9, 9, 2)
• Incorrect output: 9 (due to setting second_highest = 9 when seeing the second 9)

Correct Solution: Use strict inequality (>) to ensure we only update when finding a truly larger value:

if digit_value > highest:  # Correct: strict inequality
    second_highest = highest
    highest = digit_value

Pitfall 2: Using a Set to Collect All Digits First

The Problem: While using a set seems intuitive for finding unique digits, it requires extra space and two passes through the data.

Inefficient Approach:

digits = set()
for char in s:
    if char.isdigit():
        digits.add(int(char))
sorted_digits = sorted(digits, reverse=True)
return sorted_digits[1] if len(sorted_digits) >= 2 else -1

Issues:

• Space complexity increases to O(10) for the set
• Time complexity becomes O(n + 10log10) due to sorting
• Less elegant and more code

Better Solution: The two-variable tracking approach maintains O(1) space and O(n) time while being more concise.

Pitfall 3: Forgetting the Boundary Condition for Second Highest Update

The Problem: When updating the second highest, forgetting to check that the new value is also less than the highest can lead to incorrect results.

Incorrect Implementation:

elif digit_value > second_highest:  # Wrong: missing upper bound check
    second_highest = digit_value

Example Where It Fails:

• Input: "a5b5c5"
• After seeing first 5: highest = 5, second_highest = -1
• After seeing second 5: Without the upper bound check, we might incorrectly set second_highest = 5
• Result: Returns 5 instead of -1

Correct Solution: Always check both bounds:

elif second_highest < digit_value < highest:  # Correct: check both bounds
    second_highest = digit_value