1796. Second Largest Digit in a String
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 48.1%
Problem Breakdown
The problem requires finding the second largest numerical digit in an alphanumeric string. The input is a string s consisting of lowercase English letters and digits. The output should be the second largest unique digit found in the string, or -1 if there is no such digit.
Inputs:
- A single string
s(1 <= s.length <= 500)
Outputs:
- An integer representing the second largest unique digit, or
-1if it does not exist.
Implicit Constraints and Edge Cases:
- The string can contain duplicate digits.
- If there are fewer than two unique digits, return
-1. - The string is guaranteed to be non-empty and only contains lowercase letters and digits.
Intuition
A brute-force approach would involve iterating through the string, collecting all unique digits, sorting them, and then selecting the second largest. However, this approach has a time complexity of O(n log n) due to sorting, which can be improved.
The key insight is to use two variables to keep track of the largest and second largest unique digits as we iterate through the string. This way, we only need a single pass through the string (O(n) time complexity), making it more efficient.
Approach
- Initialize two variables,
largestandsecond_largest, to-1. These will store the largest and second largest unique digits found so far. - Iterate through each character in the string:
- If the character is a digit, convert it to an integer.
- Compare the digit with
largest:- If the digit is greater than
largest, updatesecond_largestto belargest, and then updatelargestto be the current digit. - Else if the digit is less than
largestbut greater thansecond_largest, updatesecond_largest.
- If the digit is greater than
- After iterating through the string, return
second_largest.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the string. We only make a single pass through the string.
- Space Complexity: O(1). We use a constant amount of extra space for storing the two largest digits.
Solution
def second_largest_digit(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
Edge Cases Handled
- Single unique digit: If the string contains only one unique digit,
second_largestremains-1, which is returned correctly. - All characters are letters: If there are no digits in the string, both
largestandsecond_largestremain-1, resulting in a correct return of-1. - String with duplicate largest digits: The algorithm correctly updates
second_largestonly when a new larger digit is found, ensuring that duplicates do not affect the result.