#1796

Easy

LeetCode Problem Workspace

Second Largest Digit in a String

Given a string with alphanumeric characters, find the second largest digit, or return -1 if it doesn’t exist.

Problem Statement

You are given a string consisting of lowercase English letters and digits. Your task is to return the second largest numerical digit that appears in the string. If there is no second largest digit, return -1.

The string may contain letters, but only the digits matter. Make sure to extract the digits, handle duplicates, and identify the second largest one if it exists.

Examples

Example 1

Input: s = "dfa12321afd"

Output: 2

The digits that appear in s are [1, 2, 3]. The second largest digit is 2.

Example 2

Input: s = "abc1111"

Output: -1

The digits that appear in s are [1]. There is no second largest digit.

Constraints

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

Solution Approach

Extract and Identify Distinct Digits

First, extract the digits from the string and store them in a set to ensure they are distinct. This reduces unnecessary repetitions in further steps.

Sort and Determine Second Largest

Once the distinct digits are identified, sort them in descending order. If there are at least two digits, return the second largest one. Otherwise, return -1.

Edge Case Handling

Consider cases where the string may not have any digits or only one unique digit. Return -1 in these scenarios, ensuring correct edge case handling.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of digits found in the string. Extracting digits is O(n), where n is the length of the string. Sorting the distinct digits is O(k log k), where k is the number of distinct digits (at most 10). Thus, the overall time complexity is O(n + k log k). The space complexity is O(k) due to the storage of distinct digits.

What Interviewers Usually Probe

Look for a solution that efficiently handles string parsing and digit extraction.
Ensure the candidate considers edge cases such as no digits or only one digit.
Expect a clear understanding of hash tables for removing duplicates and sorting for the second largest value.

Common Pitfalls or Variants

Common pitfalls

Failing to handle cases with fewer than two digits correctly.
Not accounting for the presence of non-digit characters in the string.
Incorrectly assuming there will always be at least two distinct digits.

Follow-up variants

What if the string contains non-digit characters only? How should the program behave?
Consider the situation where there are multiple occurrences of the largest digit, but no second largest.
What if the string has exactly two distinct digits? Ensure the program still returns the second largest.

FAQ

How do I extract digits from the string?

You can use Python's isdigit() method to identify and extract digits from the string.

What if there are fewer than two distinct digits?

In this case, return -1, as there is no second largest digit available.

What is the time complexity of the solution?

The time complexity is O(n + k log k), where n is the length of the string and k is the number of distinct digits.

Can I use a hash table for storing digits?

Yes, a hash table (or set) can be used to store distinct digits efficiently.

What happens if there are multiple occurrences of the same digit?

Only distinct digits should be considered when finding the second largest digit.

terminal

Solution

Solution 1: One Pass

We define $a$ and $b$ to represent the largest and second largest numbers in the string, initially $a = b = -1$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def secondHighest(self, s: str) -> int:
        a = b = -1
        for c in s:
            if c.isdigit():
                v = int(c)
                if v > a:
                    a, b = v, a
                elif b < v < a:
                    b = v
        return b

Solution 2: Bit Manipulation

We can use an integer $mask$ to mark the numbers that appear in the string, where the $i$-th bit of $mask$ indicates whether the number $i$ has appeared.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def secondHighest(self, s: str) -> int:
        a = b = -1
        for c in s:
            if c.isdigit():
                v = int(c)
                if v > a:
                    a, b = v, a
                elif b < v < a:
                    b = v
        return b

Continue Practicing

#1790 check if one string swap can make strings equal #1805 number of different integers in a string #1807 evaluate the bracket pairs of a string