Skip to main content
Talentd

Second Largest Digit in a String - Solution & Explanation

EasyHash TableString19 min readAsked at: Microsoft, Meta, Google +1
Practice this problem

Problem Statement

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 <= 500
  • s consists 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.

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).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n). Space Complexity: O(1).
Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n). Space Complexity: O(1).
Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

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).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Set for Unique Values and SortingTime Complexity: O(n). Space Complexity: O(1).
Approach 2: Using Two Variables to Track Top Two Distinct NumbersTime Complexity: O(n). Space Complexity: O(1).
One Pass—
Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set for Unique Values and SortingO(n + k log k)O(k)Simple implementation when clarity matters more than optimal memory
Two Variables Tracking Top Two DigitsO(n)O(1)Best for interviews and production code due to single-pass constant space

Video Solution

Leetcode | 1796. Second Largest Digit in a String | Easy | Java Solution • Developer Docs • 1,847 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Second Largest Digit in a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Remove Digit From Number to Maximize Result