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.
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; }}Video 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.