Second Largest Digit in a String
EasyPrompt
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 <= 500sconsists of only lowercase English letters and digits.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves extracting all the numerical digits from the string, storing them in a list, sorting the list, and then finding the second largest unique digit.
Algorithm
- Create an empty list of integers, say
digits. - Iterate through each character of the input string
s. - If the character is a digit, convert it to an integer and add it to the
digitslist. - After populating the list, sort it in ascending order.
- Find the largest element, which is the last one in the sorted list.
- Iterate backwards from the second-to-last element. The first element that is strictly less than the largest element is the second largest digit.
- If no such element is found (meaning all digits were the same), return -1. Otherwise, return the found digit.
Walkthrough
The core idea is to collect every digit, sort them, and then find the second unique largest value from the end of the sorted list. This is a straightforward but inefficient method due to storing and sorting all digits, including duplicates.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int secondHighest(String s) { List<Integer> digits = new ArrayList<>(); for (char c : s.toCharArray()) { if (Character.isDigit(c)) { digits.add(c - '0'); } } if (digits.isEmpty()) { return -1; } Collections.sort(digits); int largest = digits.get(digits.size() - 1); for (int i = digits.size() - 2; i >= 0; i--) { if (digits.get(i) < largest) { return digits.get(i); } } return -1; // All digits were the same }}Complexity
Time
O(K log K), where K is the number of digits in the string `s`. In the worst case, the entire string consists of digits, making the complexity O(N log N), where N is the length of the string. Sorting the list of digits dominates the time complexity.
Space
O(K), where K is the number of digits. In the worst case, this is O(N), as we need to store all digits in a list.
Trade-offs
Pros
Relatively straightforward to conceptualize and implement.
Cons
Inefficient in both time and space, especially for strings with many digits.
Requires extra logic to handle duplicate digits after sorting.
A more optimized approach is to use a HashSet to store only the unique digits encountered. This avoids storing duplicates and simplifies finding the second largest element.
Algorithm
- Initialize an empty
HashSetof integers to store unique digits. - Iterate through each character of the input string
s. - If the character is a digit, convert it to an integer and add it to the
HashSet. - After the iteration, check the size of the set. If it's less than 2, return -1.
- Convert the
HashSetto aListand sort it in ascending order. - The second largest digit is now at the second-to-last index of the sorted list. Return this value.
Walkthrough
This approach improves upon the brute-force method by using a HashSet to automatically handle duplicate digits. This simplifies the logic and improves performance as the number of unique digits is small and constant (at most 10).
import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.List;import java.util.Set; class Solution { public int secondHighest(String s) { Set<Integer> uniqueDigits = new HashSet<>(); for (char c : s.toCharArray()) { if (Character.isDigit(c)) { uniqueDigits.add(c - '0'); } } if (uniqueDigits.size() < 2) { return -1; } List<Integer> sortedDigits = new ArrayList<>(uniqueDigits); Collections.sort(sortedDigits); return sortedDigits.get(sortedDigits.size() - 2); }}Complexity
Time
O(N), where N is the length of the string. Iterating through the string takes O(N). Adding to a `HashSet` takes O(1) on average. The number of unique digits is at most 10, so converting the set to a list and sorting it takes constant time. Thus, the overall complexity is dominated by the initial string traversal.
Space
O(1). The `HashSet` will store at most 10 unique digits (0-9), so the space required is constant.
Trade-offs
Pros
Time and space efficient.
The use of a
Setelegantly handles duplicate digits.
Cons
Involves overhead from creating data structures (
Set,List) and calling a sort function, which can be slightly slower in practice than a single-pass approach.
The most efficient method is to find the two largest unique digits in a single pass through the string, using only two variables to track the largest and second largest digits found so far.
Algorithm
- Initialize two integer variables,
firstMaxandsecondMax, to -1. - Iterate through each character of the input string
s. - If the character is a digit, convert it to its integer value,
digit. - Compare
digitwithfirstMaxandsecondMax:- If
digit > firstMax: UpdatesecondMax = firstMaxandfirstMax = digit. - Else if
digit < firstMaxanddigit > secondMax: UpdatesecondMax = digit.
- If
- After the loop, return
secondMax.
Walkthrough
This is the most optimal approach. It finds the result by iterating through the string just once, keeping track of the two largest unique digits seen so far without using any extra data structures. This avoids the overhead of collections and sorting, resulting in the best performance.
class Solution { public int secondHighest(String s) { int firstMax = -1; int secondMax = -1; for (char c : s.toCharArray()) { if (Character.isDigit(c)) { int digit = c - '0'; if (digit > firstMax) { secondMax = firstMax; firstMax = digit; } else if (digit < firstMax && digit > secondMax) { secondMax = digit; } } } return secondMax; }}Complexity
Time
O(N), where N is the length of the string. We perform a single pass over the string.
Space
O(1). We only use a few variables to store the state, regardless of the input string size.
Trade-offs
Pros
Optimal time and space complexity.
Fastest practical solution due to low overhead and a single loop without extra data structures.
Cons
The logic can be slightly more complex to write correctly compared to the
Set-based approach.
Solutions
Solution
class Solution {public int secondHighest(String s) { int a = -1, b = -1; for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); if (Character.isDigit(c)) { int v = c - '0'; if (v > a) { b = a; a = v; } else if (v > b && v < a) { b = v; } } } return b; }}class Solution {public: int secondHighest(string s) { int a = -1, b = -1; for (char &c : s) { if (isdigit(c)) { int v = c - '0'; if (v > a) { b = a, a = v; } else if (v > b && v < a) { b = v; } } } return b; }};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 bVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.