LeetCode 1796 - Second Largest Digit in a String

LeetCode Problem 1796

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem gives us a string s that contains lowercase English letters and numerical digits. Our task is to find the second largest distinct digit that appears anywhere in the string.

The important detail is that we care about distinct digits, not frequency. If the string contains "111222333", the distinct digits are {1, 2, 3}. The largest digit is 3, so the second largest digit is 2.

If there is only one unique digit in the string, then no second largest digit exists, and we must return -1.

For example, in the string "dfa12321afd", the digits present are 1, 2, and 3. The largest digit is 3, so the second largest is 2.

The constraints are small:

• 1 <= s.length <= 500
• The string contains only lowercase letters and digits

Because the input size is small, even less efficient solutions would still work comfortably. However, the problem is designed to test clean string processing and careful handling of distinct values.

Several edge cases are important:

• A string with no digits at all, such as "abcdef", should return -1.
• A string with only one unique digit repeated many times, such as "1111", should also return -1.
• Digits may appear in any order, so we cannot assume the second largest digit appears near the end.
• Duplicate digits must not affect the result. We only care about distinct values.

Approaches

Brute Force Approach

A straightforward solution is to scan the string and collect all distinct digits into a set. After processing the entire string, we can sort the distinct digits in descending order and return the second element if it exists.

This works because a set automatically removes duplicates, leaving only unique digits. Sorting then gives us the digits in numerical order.

For example:

• Input: "dfa12321afd"
• Distinct digits: {1, 2, 3}
• Sorted descending: [3, 2, 1]
• Second largest: 2

Although this approach is perfectly acceptable for the given constraints, it performs extra work by sorting all digits even though there are at most only 10 possible digits.

Optimal Approach

The key observation is that there are only 10 possible digits, from 0 to 9. Instead of storing and sorting all digits, we can track the largest and second largest distinct digits while scanning the string once.

We maintain two variables:

• largest
• second_largest

As we encounter each digit:

• If it is larger than largest, then the old largest becomes second_largest
• If it is between largest and second_largest, we update second_largest
• Duplicate digits are ignored

This allows us to compute the answer in a single pass with constant extra space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + k log k)	O(k)	Uses a set and sorts distinct digits
Optimal	O(n)	O(1)	Tracks largest and second largest directly

Here, k is the number of distinct digits, and k <= 10.

Algorithm Walkthrough

1. Initialize two variables, largest and second_largest, to -1.

These variables will track the two biggest distinct digits seen so far. Using -1 works because all valid digits are between 0 and 9. 2. Iterate through each character in the string.

We examine every character because digits can appear anywhere in the input. 3. Check whether the current character is a digit.

If the character is a letter, we skip it because only numerical digits matter. 4. Convert the digit character into an integer.

For example, '3' becomes 3. 5. Compare the digit with largest.

If the digit is greater than largest, then:

• Move the current largest into second_largest
• Update largest with the new digit

This preserves the two highest distinct digits seen so far. 6. Otherwise, check whether the digit should become second_largest.

The digit becomes the new second_largest if:

• It is different from largest
• It is greater than second_largest

7. Continue until the entire string has been processed.
8. Return second_largest.

If no valid second largest digit exists, the variable will still be -1.

Why it works

At every step of the scan, the algorithm maintains the invariant that:

• largest stores the biggest distinct digit encountered so far
• second_largest stores the second biggest distinct digit encountered so far

Whenever a new larger digit appears, the previous maximum becomes the second maximum. Whenever a digit falls strictly between the two tracked values, it updates the second maximum. Since every digit is processed exactly once, the final value of second_largest is guaranteed to be correct.

Python Solution

class Solution:
    def secondHighest(self, s: str) -> int:
        largest = -1
        second_largest = -1

        for char in s:
            if char.isdigit():
                digit = int(char)

                if digit > largest:
                    second_largest = largest
                    largest = digit
                elif largest > digit > second_largest:
                    second_largest = digit

        return second_largest

The implementation begins by initializing largest and second_largest to -1. These variables track the two largest distinct digits encountered during traversal.

The loop processes each character in the string. The isdigit() method filters out letters so that only numerical characters are considered.

When a digit is found, it is converted to an integer for numerical comparison.

If the digit exceeds the current largest, the old maximum is shifted into second_largest, and the new digit becomes largest.

The elif condition handles the case where the digit is smaller than largest but still larger than second_largest. The condition largest > digit > second_largest also prevents duplicates from incorrectly updating the result.

Finally, the method returns second_largest. If no second distinct digit exists, the value remains -1.

Go Solution

func secondHighest(s string) int {
    largest := -1
    secondLargest := -1

    for _, ch := range s {
        if ch >= '0' && ch <= '9' {
            digit := int(ch - '0')

            if digit > largest {
                secondLargest = largest
                largest = digit
            } else if digit < largest && digit > secondLargest {
                secondLargest = digit
            }
        }
    }

    return secondLargest
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a direct equivalent of Python's isdigit() for rune values, we manually check whether the character lies between '0' and '9'.

The conversion from rune to integer is done using:

digit := int(ch - '0')

Go uses explicit integer handling, but overflow is not a concern because digits are limited to the range 0 through 9.

Worked Examples

Example 1

Input:

s = "dfa12321afd"

Processing steps:

Character	Digit?	largest	second_largest
d	No	-1	-1
f	No	-1	-1
a	No	-1	-1
1	Yes	1	-1
2	Yes	2	1
3	Yes	3	2
2	Yes	3	2
1	Yes	3	2
a	No	3	2
f	No	3	2
d	No	3	2

Final result:

2

Example 2

Input:

s = "abc1111"

Processing steps:

Character	Digit?	largest	second_largest
a	No	-1	-1
b	No	-1	-1
c	No	-1	-1
1	Yes	1	-1
1	Yes	1	-1
1	Yes	1	-1
1	Yes	1	-1

Final result:

-1

There is only one distinct digit, so no second largest digit exists.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only two integer variables are used

The algorithm scans the string a single time, so the runtime grows linearly with the length of the input string.

The space usage remains constant because we only store two integers regardless of input size.

Test Cases

solution = Solution()

assert solution.secondHighest("dfa12321afd") == 2  # standard mixed input
assert solution.secondHighest("abc1111") == -1  # only one distinct digit
assert solution.secondHighest("ck077") == 0  # digits 0 and 7
assert solution.secondHighest("abc") == -1  # no digits present
assert solution.secondHighest("9876543210") == 8  # all digits present
assert solution.secondHighest("000999") == 0  # repeated largest and second largest
assert solution.secondHighest("5") == -1  # single digit only
assert solution.secondHighest("a1b2c3d4") == 3  # increasing digits
assert solution.secondHighest("a9a8a7") == 8  # descending digits
assert solution.secondHighest("111222333") == 2  # duplicates should not matter
assert solution.secondHighest("1a2b2c1") == 1  # only two distinct digits
assert solution.secondHighest("9abc8xyz7") == 8  # scattered digits

Test	Why
"dfa12321afd"	Validates the primary example
"abc1111"	Ensures duplicate digits do not count multiple times
"ck077"	Tests handling of zero
"abc"	Verifies behavior with no digits
"9876543210"	Tests all possible digits
"000999"	Ensures repeated values are ignored correctly
"5"	Tests single digit input
"a1b2c3d4"	Verifies increasing digit order
"a9a8a7"	Verifies decreasing digit order
"111222333"	Confirms distinct digit logic
"1a2b2c1"	Tests exactly two distinct digits
"9abc8xyz7"	Ensures non-adjacent digits work correctly

Edge Cases

One important edge case occurs when the string contains no digits at all. For example, "abcdef" has no numerical characters. A naive implementation that assumes at least one digit exists could fail or produce an invalid result. In this solution, both tracking variables remain -1, so the algorithm correctly returns -1.

Another critical edge case is when the string contains only one distinct digit repeated many times, such as "111111". A buggy solution might accidentally treat repeated occurrences as separate values and incorrectly return 1. The condition largest > digit > second_largest prevents duplicates from updating the second largest value.

A third edge case involves the digit 0. Since 0 is a valid digit, implementations that rely on truthy or falsy checks may accidentally ignore it. For example, "700" should return 0 because the distinct digits are {7, 0}. This implementation handles 0 correctly because all comparisons are numerical and use explicit integer values rather than boolean checks.

A final edge case is when digits appear in arbitrary order, such as "5a3b9c1". The second largest digit may appear before or after the largest digit. Because the algorithm continuously updates both tracking variables during traversal, the ordering of characters does not affect correctness.