Second Largest Digit in a String solution and explanation
Google
9 more videos on this problem
Leetcode | 1796. Second Largest Digit in a String | Easy | Java SolutionDeveloper Docs · 7:37 · 1K views
Leetcode 1796. Second Largest Digit in a String [Java]if else statement · 4:24 · 997 views
LeetCode 1796 Second Largest Digit in a StringAlgorithmicIQ · 6:14 · 731 views
1796. Second Largest Digit in a String || In Java || Leetcode || Easy #leetcodeQuick Learning With Sree · 5:57 · 593 views
1796. Second Largest Digit in a String (Leetcode Easy)Programming Live with Larry · 4:41 · 510 views
Second largest digit in a string in 30 seconds - Leetcode 1796 - PythonTop SWE · 0:26 · 350 views
Solution of LeetCode 1796 | Second Largest Digit in a StringInterCoding · 8:26 · 300 views
🔥 Easy Leetcode Problem 1796 | Second Largest Digit in a String&BEYOND · 8:50 · 256 views
Second Largest Digit in a String - LeetCode 1796 - Java Solutionalgobest - Computer Science · 2:55 · 170 views
Leetcode solving: 1796. Second Largest Digit in a StringMath Geeks · 1:54 · 128 views
The problem
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.
Approach overview
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.
Approach 1: Approach 1: Using Set for Unique Values and Sorting
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.
def secondHighest(s: str) -> int:
digits = {int(c) for c in s if c.isdigit()}
sorted_digits = sorted(digits, reverse=True)
return sorted_digits[1] if len(sorted_digits) > 1 else -1
print(secondHighest("dfa12321afd"))import java.util.Set;
import java.util.TreeSet;
class Solution {
public int secondHighest(String s) {
Set<Integer> digits = new TreeSet<>();
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
digits.add(c - '0');
}
}
if (digits.size() < 2) return -1;
return (int) digits.toArray()[digits.size() - 2];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.secondHighest("dfa12321afd"));
}
}#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
int secondHighest(std::string s) {
std::set<int> digits;
for (char c : s) {
if (isdigit(c)) {
digits.insert(c - '0');
}
}
if (digits.size() < 2) return -1;
auto it = digits.rbegin();
++it;
return *it;
}
int main() {
std::string s = "dfa12321afd";
std::cout << secondHighest(s) << std::endl;
return 0;
}function secondHighest(s) {
let digits = new Set();
for (let char of s) {
if (!isNaN(char)) {
digits.add(parseInt(char));
}
}
if (digits.size < 2) return -1;
let sortedDigits = Array.from(digits).sort((a, b) => b - a);
return sortedDigits[1];
}
console.log(secondHighest("dfa12321afd"));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int secondHighest(char *s) {
int digits[10] = {0};
int i, count = 0;
for (i = 0; s[i] != '\0'; i++) {
if (s[i] >= '0' && s[i] <= '9') {
digits[s[i] - '0'] = 1;
}
}
for (i = 9; i >= 0; i--) {
if (digits[i]) {
count++;
}
if (count == 2) {
return i;
}
}
return -1;
}
int main() {
char s[] = "dfa12321afd";
printf("%d\n", secondHighest(s));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
public int SecondHighest(string s) {
HashSet<int> digits = new HashSet<int>();
foreach (char c in s) {
if (char.IsDigit(c)) {
digits.Add(c - '0');
}
}
if (digits.Count < 2) return -1;
return digits.OrderByDescending(x => x).Skip(1).First();
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.SecondHighest("dfa12321afd"));
}
}This Python solution uses set comprehension to extract unique digits, then sorts the set to find the second largest digit. If less than two digits exist, it returns -1.
Approach 2: Approach 2: Using Two Variables to Track Top Two Distinct Numbers
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.
def secondHighest(s: str) -> int:
first, second = -1, -1
for char in s:
if char.isdigit():
digit = int(char)
if digit > first:
second = first
first = digit
elif digit < first and digit > second:
second = digit
return second
print(secondHighest("dfa12321afd"))class Solution {
public int secondHighest(String s) {
int first = -1, second = -1;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
int digit = c - '0';
if (digit > first) {
second = first;
first = digit;
} else if (digit < first && digit > second) {
second = digit;
}
}
}
return second;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.secondHighest("dfa12321afd"));
}
}#include <iostream>
#include <string>
#include <limits.h>
int secondHighest(std::string s) {
int first = -1, second = -1;
for (char c : s) {
if (isdigit(c)) {
int digit = c - '0';
if (digit > first) {
second = first;
first = digit;
} else if (digit < first && digit > second) {
second = digit;
}
}
}
return second;
}
int main() {
std::string s = "dfa12321afd";
std::cout << secondHighest(s) << std::endl;
return 0;
}function secondHighest(s) {
let first = -1, second = -1;
for (let char of s) {
if (!isNaN(char)) {
let digit = parseInt(char);
if (digit > first) {
second = first;
first = digit;
} else if (digit < first && digit > second) {
second = digit;
}
}
}
return second;
}
console.log(secondHighest("dfa12321afd"));#include <stdio.h>
#include <limits.h>
int secondHighest(char* s) {
int largest = -1, secondLargest = -1;
while (*s) {
if (*s >= '0' && *s <= '9') {
int num = *s - '0';
if (num > largest) {
secondLargest = largest;
largest = num;
} else if (num < largest && num > secondLargest) {
secondLargest = num;
}
}
s++;
}
return secondLargest;
}
int main() {
char s[] = "dfa12321afd";
printf("%d\n", secondHighest(s));
return 0;
}using System;
class Solution {
public int SecondHighest(string s) {
int first = -1, second = -1;
foreach (char c in s) {
if (char.IsDigit(c)) {
int digit = c - '0';
if (digit > first) {
second = first;
first = digit;
} else if (digit < first && digit > second) {
second = digit;
}
}
}
return second;
}
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.SecondHighest("dfa12321afd"));
}
}This Python solution initializes two variables, first and second, to manage the largest and second largest distinct digits seen while iterating through the input string, updating them as necessary based on the digit encountered.
Approach 3: One Pass
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).
function secondHighest(s: string): number {
let first = -1;
let second = -1;
for (const c of s) {
if (c >= '0' && c <= '9') {
const num = c.charCodeAt(0) - '0'.charCodeAt(0);
if (first < num) {
[first, second] = [num, first];
} else if (first !== num && second < num) {
second = num;
}
}
}
return second;
}func secondHighest(s string) int {
a, b := -1, -1
for _, c := range s {
if c >= '0' && c <= '9' {
v := int(c - '0')
if v > a {
b, a = a, v
} else if v > b && v < a {
b = v
}
}
}
return b
}impl Solution {
pub fn second_highest(s: String) -> i32 {
let mut first = -1;
let mut second = -1;
for c in s.as_bytes() {
if char::is_digit(*c as char, 10) {
let num = (c - b'0') as i32;
if first < num {
second = first;
first = num;
} else if num < first && second < num {
second = num;
}
}
}
second
}
}Approach 4: Bit Manipulation
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).
func secondHighest(s string) int {
mask := 0
for _, c := range s {
if c >= '0' && c <= '9' {
mask |= 1 << int(c-'0')
}
}
for i, cnt := 9, 0; i >= 0; i-- {
if mask>>i&1 == 1 {
cnt++
if cnt == 2 {
return i
}
}
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Set for Unique Values and Sorting | Time Complexity: O(n + k log k), where k is the number of unique digits. Space Complexity: O(k). |
| Approach 2: Using Two Variables to Track Top Two Distinct Numbers | Time Complexity: O(n). Space Complexity: O(1). |
| One Pass | – |
| Bit Manipulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Second Largest Digit in a String easy or hard?
The problem is categorized as Easy on LeetCode with an acceptance rate around 54%. The main challenge is ensuring digits are distinct while correctly updating the two largest values during a single pass.
Second Largest Digit in a String Python/Java solution
Python and Java implementations usually follow the same pattern: iterate through the string, check if each character is a digit, convert it to an integer, and update the largest and second largest variables. The logic stays identical across languages with O(n) time and O(1) space.
How to solve Second Largest Digit in a String in O(n)?
Iterate through the string and process only numeric characters. Maintain two variables: the largest digit and the second largest distinct digit. Update them whenever a larger value appears or when a value falls between the current two. This single-pass approach guarantees O(n) time and constant space.
What is the best approach for Second Largest Digit in a String?
The most efficient approach is scanning the string once while tracking the two largest distinct digits using two variables. This avoids extra data structures and sorting. The algorithm runs in O(n) time and O(1) space because only two values are stored while iterating through the string.
Is Second Largest Digit in a String asked at Google/Amazon/Meta?
Problems involving scanning strings and tracking top elements appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the pattern of maintaining the top two values in one pass is a common interview technique.
What data structure is used in Second Largest Digit in a String?
Two common choices appear in solutions. A set can store unique digits before sorting them to find the second largest. The optimal solution avoids extra structures and instead uses two integer variables to track the largest and second largest digits during iteration.
What is the time complexity of Second Largest Digit in a String?
The optimal solution runs in O(n) time where n is the length of the string. Each character is inspected once to check whether it is a digit and potentially update the top two values. Space complexity is O(1) because only two variables are used to track the largest and second largest digits.