Second Largest Digit in a String

Difficulty: Easy | Acceptance: 54.30% | Paid: No Topics: Hash Table, String

Given an alphanumeric string s, return the second largest numerical digit that appears in s, or -1 if it does not exist.

An alphanumeric string is a string consisting of lowercase English letters and uppercase English letters and digits.

• Examples
• Constraints
• Set + Sort Approach
• Two Pass Approach
• Single Pass Approach

Examples

Input: s = "dfa12321afd"
Output: 2
Explanation: The digits are [1, 2, 3]. The second largest digit is 2.

Input: s = "abc1111"
Output: -1
Explanation: The digits are [1]. There is no second largest digit.

Constraints

1 <= s.length <= 500
s consists of lowercase English letters and/or digits.

Set + Sort Approach

Intuition Extract all unique digits using a set, sort them, and return the second largest.

Steps

• Iterate through the string and collect all digits in a set
• If the set has fewer than 2 elements, return -1
• Sort the set and return the second largest element

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

Complexity

• Time: O(n log n) where n is the length of the string (due to sorting)
• Space: O(1) since there are at most 10 unique digits
• Notes: Simple but sorting is unnecessary for this problem

Two Pass Approach

Intuition First pass finds the maximum digit, second pass finds the largest digit less than the maximum.

Steps

• First pass: find the maximum digit in the string
• Second pass: find the largest digit that is strictly less than the maximum
• Return the result, or -1 if no such digit exists

class Solution:
    def secondHighest(self, s: str) -> int:
        max_digit = -1
        for c in s:
            if c.isdigit():
                max_digit = max(max_digit, int(c))
        
        second_max = -1
        for c in s:
            if c.isdigit():
                d = int(c)
                if d < max_digit:
                    second_max = max(second_max, d)
        
        return second_max

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1)
• Notes: Two passes through the string but no extra space needed

Single Pass Approach

Intuition Track both the largest and second largest digits in a single pass through the string.

Steps

• Initialize first and second to -1
• For each digit in the string:
  • If it’s greater than first, update second to first and first to the digit
  • If it’s between first and second, update second
• Return second

class Solution:
    def secondHighest(self, s: str) -> int:
        first = -1
        second = -1
        for c in s:
            if c.isdigit():
                d = int(c)
                if d > first:
                    second = first
                    first = d
                elif d < first and d > second:
                    second = d
        return second

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1)
• Notes: Most efficient approach with single pass and constant space