Jobs

Interviews

Discussions

Second Largest Digit in a String

Easy

Asked by:

9 views

Topics:

StringsArrays

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.

Try coding it in LeetCode

Second Largest Digit in a String

Easy

Asked by:

9 views

Topics:

StringsArrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

To clarify the term 'second largest', if the input string is 'a9988', are we looking for the second largest *unique* digit? In this case, would the answer be 8?
Could you confirm the condition for returning -1? Is it correct to return -1 if the string contains fewer than two distinct digits, such as in 'abc' which has none, or 'a111' which has only one?
The problem states the input consists of 'lowercase English letters and digits'. Can I assume the input will strictly adhere to this format, and I don't need to handle uppercase letters, spaces, or other special characters?
The length constraint is `1 <= s.length <= 500`. Does this guarantee the input string will never be empty? And should my solution account for a potential `null` input?
Just to be certain, are we exclusively dealing with the base-10 digits '0' through '9'?

Brute Force Solution

Approach

The plan is to first go through the text and gather all the unique numerical digits we see. Once we have this group of numbers, we can easily identify the largest one, and then find the largest among the remaining numbers.

Here's how the algorithm would work step-by-step:

First, create a fresh, empty collection to keep track of the different numbers we find.
Look at the original piece of text, one symbol at a time from beginning to end.
For each symbol, decide if it's a numerical digit.
If it is a digit, add it to your collection, but only if you haven't added that same digit before. This ensures we only have one of each digit.
After you've gone through the entire text, look at your collection of unique digits.
If your collection contains fewer than two digits, it's impossible to find a second largest, so you report that.
If you have at least two digits, first find the single biggest digit in the collection.
Next, ignore that biggest digit and look at what's left in the collection.
Finally, find the biggest digit among the remaining ones. That's your answer.

Code Implementation

def second_largest_digit(alphanumeric_string):
    # Using a set ensures we only store each digit once, fulfilling the unique digits requirement.

    unique_digit_collection = set()

    for current_character in alphanumeric_string:
        if current_character.isdigit():
            unique_digit_collection.add(int(current_character))

    # We must have at least two unique digits to be able to find a second largest one.

    if len(unique_digit_collection) < 2:
        return -1

    # Sorting the unique digits in descending order places the second largest at a known index.

    sorted_list_of_digits = sorted(list(unique_digit_collection), reverse=True)

    return sorted_list_of_digits[1]

Big(O) Analysis

Time Complexity

O(n) – Let n be the length of the input string. The algorithm's cost is driven by the single loop that iterates through each of the n characters in the string. Inside this loop, checking if a character is a digit and adding it to a unique collection are constant time operations. After the loop completes, finding the largest and second-largest values in a collection of at most 10 unique digits also takes constant time. Therefore, the total work is directly proportional to n, which simplifies to a linear time complexity of O(n).

Space Complexity

O(1) – The primary auxiliary space is used by the collection created to store the unique numerical digits encountered in the string. As per the problem description, this collection only stores digits from '0' through '9'. Because there are at most 10 possible unique digits, the size of this collection is capped at a maximum of 10 elements. This size is constant and does not grow with the length of the input string, N, resulting in an O(1) space complexity.

Optimal Solution

Approach

The most efficient way to solve this is to read through the string just once. While reading, we'll keep track of the largest digit and the second-largest digit we have found so far, updating them as we go.

Here's how the algorithm would work step-by-step:

Prepare to keep track of two numbers: the largest digit found so far and the second-largest digit found so far. Initially, we can consider both to be empty or nonexistent.
Examine the input text one character at a time from beginning to end.
If the character is a letter or symbol, simply skip it and move to the next one.
When you encounter a numerical digit, first compare it to the largest digit you are currently tracking.
If this new digit is greater than your current largest, this new one becomes the largest, and your old largest is now considered the second-largest.
If the new digit is not the absolute largest, then check if it's smaller than the largest but bigger than your second-largest. If so, it becomes the new second-largest.
After going through the entire text, the number you are holding as the second-largest is the final answer. If you never found a second-largest number to track, it means one doesn't exist.

Code Implementation

def second_highest(input_string: str) -> int:
    # We use -1 as a starting point because it's smaller than any possible digit.
    largest_seen_digit = -1
    second_largest_seen_digit = -1

    for character in input_string:
        if character.isdigit():
            current_digit_value = int(character)

            # If a new largest digit is found, the previous largest becomes the second largest.
            if current_digit_value > largest_seen_digit:
                second_largest_seen_digit = largest_seen_digit
                largest_seen_digit = current_digit_value

            # This case is for a digit that is not the new largest, but could be the second largest.
            elif current_digit_value < largest_seen_digit and current_digit_value > second_largest_seen_digit:
                second_largest_seen_digit = current_digit_value

    return second_largest_seen_digit

Big(O) Analysis

Time Complexity

O(n) – Let n be the length of the input string. The described approach processes the string in a single pass, examining each character exactly once. For each character, it performs a constant number of operations, such as checking if it's a digit and comparing it with the two tracked numbers. Since the total work is directly proportional to the number of characters in the string, the time complexity is linear, which simplifies to O(n).

Space Complexity

O(1) – The space complexity is constant because the algorithm only needs to store a fixed number of variables. Specifically, it uses two variables to 'keep track of' the largest and second-largest digits found so far. The amount of memory required for these variables does not grow with the length of the input string, N. Since the auxiliary space usage is independent of the input size, the complexity is O(1).

Edge Cases

Case	How to Handle
An input string that contains only letters and no digits, such as 'abcde'.	The solution will find no digits and correctly return -1, the default value for when no second largest digit exists.
An input string containing multiple occurrences of only one unique digit, like 'a111b1'.	The algorithm identifies the largest digit but fails to find a second one, properly returning -1.
The largest and second-largest digits appear multiple times and out of order, like 'xyz4848'.	The algorithm correctly processes duplicates without altering the already stored largest and second-largest values, ensuring the result is based on unique values.
An input string where the second-largest digit is 0, such as 'ab10'.	The algorithm correctly handles 0 as a valid digit and can identify it as the second largest.
An input string containing all unique digits from 0 to 9, for instance '9876543210'.	The solution correctly identifies 9 as the largest and 8 as the second largest, regardless of their position in the string.
A string with only one character, which could be a letter ('a') or a digit ('7').	The solution processes the single character and returns -1, as a second-largest digit cannot exist with fewer than two unique digits.
An input string at the maximum allowed length of 500 characters.	The single-pass solution with constant extra space scales efficiently and handles the maximum input size without performance issues.
An empty string input, which is technically disallowed by the constraints.	While constraints guarantee a non-empty string, a robust solution would handle this by returning -1 immediately.

An input string that contains only letters and no digits, such as 'abcde'.

How to Handle:

The solution will find no digits and correctly return -1, the default value for when no second largest digit exists.

An input string containing multiple occurrences of only one unique digit, like 'a111b1'.

How to Handle:

The algorithm identifies the largest digit but fails to find a second one, properly returning -1.

The largest and second-largest digits appear multiple times and out of order, like 'xyz4848'.

How to Handle:

The algorithm correctly processes duplicates without altering the already stored largest and second-largest values, ensuring the result is based on unique values.

An input string where the second-largest digit is 0, such as 'ab10'.

How to Handle:

The algorithm correctly handles 0 as a valid digit and can identify it as the second largest.

An input string containing all unique digits from 0 to 9, for instance '9876543210'.

How to Handle:

The solution correctly identifies 9 as the largest and 8 as the second largest, regardless of their position in the string.

A string with only one character, which could be a letter ('a') or a digit ('7').

How to Handle:

The solution processes the single character and returns -1, as a second-largest digit cannot exist with fewer than two unique digits.

An input string at the maximum allowed length of 500 characters.

How to Handle:

The single-pass solution with constant extra space scales efficiently and handles the maximum input size without performance issues.

An empty string input, which is technically disallowed by the constraints.

How to Handle:

While constraints guarantee a non-empty string, a robust solution would handle this by returning -1 immediately.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

To clarify the term 'second largest', if the input string is 'a9988', are we looking for the second largest *unique* digit? In this case, would the answer be 8?
Could you confirm the condition for returning -1? Is it correct to return -1 if the string contains fewer than two distinct digits, such as in 'abc' which has none, or 'a111' which has only one?
The problem states the input consists of 'lowercase English letters and digits'. Can I assume the input will strictly adhere to this format, and I don't need to handle uppercase letters, spaces, or other special characters?
The length constraint is `1 <= s.length <= 500`. Does this guarantee the input string will never be empty? And should my solution account for a potential `null` input?
Just to be certain, are we exclusively dealing with the base-10 digits '0' through '9'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a fresh, empty collection to keep track of the different numbers we find.
Look at the original piece of text, one symbol at a time from beginning to end.
For each symbol, decide if it's a numerical digit.
If it is a digit, add it to your collection, but only if you haven't added that same digit before. This ensures we only have one of each digit.
After you've gone through the entire text, look at your collection of unique digits.
If your collection contains fewer than two digits, it's impossible to find a second largest, so you report that.
If you have at least two digits, first find the single biggest digit in the collection.
Next, ignore that biggest digit and look at what's left in the collection.
Finally, find the biggest digit among the remaining ones. That's your answer.

Code Implementation

def second_largest_digit(alphanumeric_string):
    # Using a set ensures we only store each digit once, fulfilling the unique digits requirement.

    unique_digit_collection = set()

    for current_character in alphanumeric_string:
        if current_character.isdigit():
            unique_digit_collection.add(int(current_character))

    # We must have at least two unique digits to be able to find a second largest one.

    if len(unique_digit_collection) < 2:
        return -1

    # Sorting the unique digits in descending order places the second largest at a known index.

    sorted_list_of_digits = sorted(list(unique_digit_collection), reverse=True)

    return sorted_list_of_digits[1]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Prepare to keep track of two numbers: the largest digit found so far and the second-largest digit found so far. Initially, we can consider both to be empty or nonexistent.
Examine the input text one character at a time from beginning to end.
If the character is a letter or symbol, simply skip it and move to the next one.
When you encounter a numerical digit, first compare it to the largest digit you are currently tracking.
If this new digit is greater than your current largest, this new one becomes the largest, and your old largest is now considered the second-largest.
If the new digit is not the absolute largest, then check if it's smaller than the largest but bigger than your second-largest. If so, it becomes the new second-largest.
After going through the entire text, the number you are holding as the second-largest is the final answer. If you never found a second-largest number to track, it means one doesn't exist.

Code Implementation

def second_highest(input_string: str) -> int:
    # We use -1 as a starting point because it's smaller than any possible digit.
    largest_seen_digit = -1
    second_largest_seen_digit = -1

    for character in input_string:
        if character.isdigit():
            current_digit_value = int(character)

            # If a new largest digit is found, the previous largest becomes the second largest.
            if current_digit_value > largest_seen_digit:
                second_largest_seen_digit = largest_seen_digit
                largest_seen_digit = current_digit_value

            # This case is for a digit that is not the new largest, but could be the second largest.
            elif current_digit_value < largest_seen_digit and current_digit_value > second_largest_seen_digit:
                second_largest_seen_digit = current_digit_value

    return second_largest_seen_digit

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
An input string that contains only letters and no digits, such as 'abcde'.	The solution will find no digits and correctly return -1, the default value for when no second largest digit exists.
An input string containing multiple occurrences of only one unique digit, like 'a111b1'.	The algorithm identifies the largest digit but fails to find a second one, properly returning -1.
The largest and second-largest digits appear multiple times and out of order, like 'xyz4848'.	The algorithm correctly processes duplicates without altering the already stored largest and second-largest values, ensuring the result is based on unique values.
An input string where the second-largest digit is 0, such as 'ab10'.	The algorithm correctly handles 0 as a valid digit and can identify it as the second largest.
An input string containing all unique digits from 0 to 9, for instance '9876543210'.	The solution correctly identifies 9 as the largest and 8 as the second largest, regardless of their position in the string.
A string with only one character, which could be a letter ('a') or a digit ('7').	The solution processes the single character and returns -1, as a second-largest digit cannot exist with fewer than two unique digits.
An input string at the maximum allowed length of 500 characters.	The single-pass solution with constant extra space scales efficiently and handles the maximum input size without performance issues.
An empty string input, which is technically disallowed by the constraints.	While constraints guarantee a non-empty string, a robust solution would handle this by returning -1 immediately.

An input string that contains only letters and no digits, such as 'abcde'.

How to Handle:

The solution will find no digits and correctly return -1, the default value for when no second largest digit exists.

An input string containing multiple occurrences of only one unique digit, like 'a111b1'.

How to Handle:

The algorithm identifies the largest digit but fails to find a second one, properly returning -1.

The largest and second-largest digits appear multiple times and out of order, like 'xyz4848'.

How to Handle:

The algorithm correctly processes duplicates without altering the already stored largest and second-largest values, ensuring the result is based on unique values.

An input string where the second-largest digit is 0, such as 'ab10'.

How to Handle:

The algorithm correctly handles 0 as a valid digit and can identify it as the second largest.

An input string containing all unique digits from 0 to 9, for instance '9876543210'.

How to Handle:

The solution correctly identifies 9 as the largest and 8 as the second largest, regardless of their position in the string.

A string with only one character, which could be a letter ('a') or a digit ('7').

How to Handle:

The solution processes the single character and returns -1, as a second-largest digit cannot exist with fewer than two unique digits.

An input string at the maximum allowed length of 500 characters.

How to Handle:

The single-pass solution with constant extra space scales efficiently and handles the maximum input size without performance issues.

An empty string input, which is technically disallowed by the constraints.

How to Handle:

While constraints guarantee a non-empty string, a robust solution would handle this by returning -1 immediately.