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 digits.
Example 1:
Input: s = "dfa12321afd" Output: 2 Explanation: The digits that appear in s are [1, 2, 3]. The second largest digit is 2.
Example 2:
Input: s = "abc1111" Output: -1 Explanation: The digits that appear in s are [1]. There is no second largest digit.
Constraints:
1 <= s.length <= 500s consists of only lowercase English letters and digits.Problem Overview: You are given an alphanumeric string that may contain letters and digits. Extract all digits and return the second largest distinct digit. If fewer than two distinct digits exist, return -1. The key detail is distinct digits — repeated values should only count once.
Approach 1: Using Set for Unique Values and Sorting (Time: O(n + k log k), Space: O(k))
Scan the string and collect every digit into a set. The set automatically removes duplicates, leaving only unique digit values. Convert the set into a list and sort it in descending order. The second element in the sorted list is the second largest digit. If the list size is less than two, return -1. This approach is straightforward and easy to reason about because the set handles uniqueness while sorting determines the ranking.
The number of possible digits is small (0–9), so sorting overhead is minimal in practice. Time complexity is O(n + k log k) where k is the number of distinct digits (at most 10). Space complexity is O(k). This solution is commonly implemented using structures from Hash Table concepts for uniqueness and basic String iteration.
Approach 2: Using Two Variables to Track Top Two Distinct Numbers (Time: O(n), Space: O(1))
Instead of storing digits, track the two largest distinct digits while scanning the string once. Maintain two variables: max1 (largest digit) and max2 (second largest digit). For every character, check if it is a digit. Convert it to an integer and update the two variables:
If the digit is greater than max1, shift max1 into max2 and update max1. If the digit is smaller than max1 but greater than max2, update max2. Skip updates when the digit equals max1 to preserve distinctness. After processing the entire string, max2 holds the answer or remains -1 if no second distinct digit exists.
This approach avoids extra storage and sorting. Every character is processed exactly once, giving O(n) time and O(1) space. The logic resembles common interview patterns where you track the top two elements during a single pass.
Recommended for interviews: Start by describing the set + sorting idea because it clearly shows how you enforce uniqueness. Then move to the single-pass two-variable approach. Interviewers usually prefer the O(n) scan because it demonstrates strong control over state tracking and avoids unnecessary data structures.
This approach involves extracting digits from the string, storing them in a set to remove duplicates, converting the set to a list, and then sorting this list to find the second largest digit. If the list doesn't contain at least two elements, return -1.
This C solution uses an array to keep track of which digits (0-9) appear in the string. After populating this array, it iterates backwards over it to find the second distinct largest digit. The time complexity is O(n) because it processes the input string in a single pass and then iterates over a fixed range of 0-9 (constant work).
This approach avoids sorting by maintaining two variables to track the largest and second largest digits directly as we scan through the string. By updating these variables based on conditions, we can achieve the desired result without additional data structures.
This C solution uses two variables, largest and secondLargest, to track the greatest and second greatest digits as it parses the string. It updates these variables based on comparisons without storing all digits in memory, making it efficient in terms of space.
We define a and b to represent the largest and second largest numbers in the string, initially a = b = -1.
We traverse the string s. If the current character is a digit, we convert it to a number v. If v > a, it means that v is the largest number currently appearing, we update b to a, and update a to v; if v < a, it means that v is the second largest number currently appearing, we update b to v.
After the traversal, we return b.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
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.
We traverse the string s. If the current character is a digit, we convert it to a number v, and set the v-th bit of mask to 1.
Finally, we traverse mask from high to low, find the second bit that is 1, and the corresponding number is the second largest number. If there is no second largest number, return -1.
The time complexity is O(n), where n is the length of the string s. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Using Set for Unique Values and Sorting | Time Complexity: O(n). Space Complexity: O(1). |
| Approach 2: Using Two Variables to Track Top Two Distinct Numbers | Time Complexity: O(n). Space Complexity: O(1). |
| One Pass | — |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set for Unique Values and Sorting | O(n + k log k) | O(k) | Simple implementation when clarity matters more than optimal memory |
| Two Variables Tracking Top Two Digits | O(n) | O(1) | Best for interviews and production code due to single-pass constant space |
Leetcode | 1796. Second Largest Digit in a String | Easy | Java Solution • Developer Docs • 1,603 views views
Watch 9 more video solutions →Practice Second Largest Digit in a String with our built-in code editor and test cases.
Practice on FleetCode