1796. Second Largest Digit in a String

EasyHash TableString
Leetcode Link

Problem Description

The problem presents a scenario where we are given an alphanumeric string s. An alphanumeric string is composed of both lowercase English letters (such as 'a' to 'z') and numerical digits (from '0' to '9'). The task is to find the second largest numerical digit within the string and return its value. If the string does not have a second largest digit, because there is either no digit at all or there is only one unique digit, then the function should return -1.

Example Cases

  • Given s = "abc123", the function should return 2 because the numerical digits in the string are 1, 2, and 3, and the second largest is 2.
  • Given s = "ck077", the function should return 0 as 0 and 7 are the only digits, where 7 is the largest and 0 is the second largest.
  • Given s = "abc", the function should return -1 because there are no numerical digits at all.

Intuition

To solve this problem, we can scan through the string character by character, checking for numeric digits. As we find each numeric digit, we compare it to two variables that are keeping track of the largest and second-largest digits found so far, let's call them a and b, respectively.

When a digit is encountered:

  1. If it's larger than a, the current largest, we update the second-largest b to be the old largest a and then set a to this new largest value.
  2. If it's not larger than a but is larger than b and not equal to a, it becomes the new second-largest, so we update b.

We initialize a and b to -1 to indicate that we haven't found any digits yet. This also serves as our return value in case we find less than two unique numeric digits. After processing all characters, b will hold our answer, being the second-largest unique digit, or remain -1 if there isn't one.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following array represent a max heap?

Solution Approach

The reference solution provided uses a simple, single-pass approach to iterate over the string and keep track of the two largest distinct digits found.

Let's go through the approach step by step:

  1. Two variables a and b are initialized to -1. These will keep track of the largest (a) and the second largest (b) numerical digits found in the string so far.

  2. We start a loop to iterate over each character c of the string s.

  3. For each character, we check if it is a digit using c.isdigit(). If it isn't a digit, we simply continue to the next iteration, ignoring all non-digit characters.

  4. If it is a digit, we convert it to an integer v using int(c).

  5. Now, we use two if conditions to update our two variables:

    • First condition: If the integer v is greater than our current largest a, it means we've found a new largest digit. So, we need to update both a and b:
      • b becomes the old largest digit (as it is now the second largest).
      • a is updated to be v, the new largest digit.
    • Second condition: If v is not greater than a but is greater than b and also not equal to a (we are looking for the second largest unique digit, distinct from the largest), then we update b to be v.

  6. After the loop is finished, the variable b will contain the second largest digit if it exists, or -1 if it doesn't.

No complex data structures or algorithms are needed here; the solution is straightforward and executed in a single pass, making it efficient with a time complexity of O(n), where n is the length of the string.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How does quick sort divide the problem into subproblems?

Example Walkthrough

Let’s take the string s = "e4k95b2" to illustrate the solution approach. We want to find the second largest numerical digit within this string.

  1. We start by initializing two variables, a and b, to -1.

  2. We begin iterating over each character of the string.

    • e: This is not a digit, so we ignore it.
    • 4: This is a digit, so we check our conditions. Since 4 is greater than a which is -1, we update a to 4 and b remains -1.
    • k: Not a digit, we ignore it.
    • 9: This is a digit, and it's greater than a which is currently 4. We assign a's value to b, so b becomes 4, then we update a to 9.
    • 5: This is a digit, but it's smaller than a (9) and greater than b (4). Here, b is updated to 5.
    • b: Not a digit, ignored.
    • 2: This is a digit; however, it is smaller than both a and b, so we don't make any changes.

  3. Having finished the loop, we’ve now determined that the largest digit in the string is 9 and the second largest is 5.

  4. We return the value of b, which is 5, as the final answer.

By following these steps, we found that the second largest digit in the string s = "e4k95b2" is 5. No further passes or complex operations were needed, and each step was simple and based only on comparison logic.

Solution Implementation

1class Solution:
2    def secondHighest(self, s: str) -> int:
3        # Initialize the highest and second highest numbers to -1
4        highest = second_highest = -1
5      
6        # Loop through each character in the string
7        for char in s:
8            # Check if the character is a digit
9            if char.isdigit():
10                # Convert the character to an integer
11                value = int(char)
12              
13                # Update the highest and second highest values if necessary
14                if value > highest:
15                    # If the value is greater than the current highest,
16                    # update the highest and bump the old highest to second highest
17                    highest, second_highest = value, highest
18                elif second_highest < value < highest:
19                    # If the value is between second highest and highest,
20                    # update the second highest
21                    second_highest = value
22      
23        # Return the second highest value found, or -1 if not found
24        return second_highest
25
1class Solution {
2    public int secondHighest(String s) {
3        // Initialize first highest and second highest numbers to -1, assuming they don't exist.
4        int firstHighest = -1, secondHighest = -1;
5
6        // Iterate over the characters of the string.
7        for (int i = 0; i < s.length(); ++i) {
8            char currentChar = s.charAt(i);
9
10            // Check if the current character is a digit.
11            if (Character.isDigit(currentChar)) {
12                int numericValue = currentChar - '0'; // Convert char to int value.
13              
14                // If the numeric value is greater than the first highest number,
15                // update the second highest to be the old first highest,
16                // and the first highest to be the new numeric value.
17                if (numericValue > firstHighest) {
18                    secondHighest = firstHighest;
19                    firstHighest = numericValue;
20                } else if (numericValue > secondHighest && numericValue < firstHighest) {
21                    // If the numeric value is not the highest, but greater than the second highest,
22                    // update the second highest.
23                    secondHighest = numericValue;
24                }
25            }
26        }
27
28        // Return the second highest number found, or -1 if no such number exists.
29        return secondHighest;
30    }
31}
32
1#include <string> // Include the string header for using the string class
2
3class Solution {
4public:
5    // Function to find the second highest digit in a string
6    int secondHighest(string str) {
7        int highest = -1;  // Initialize the highest digit as -1
8        int secondHighest = -1; // Initialize the second highest digit as -1
9      
10        // Loop over each character in the string
11        for (const char& ch : str) {
12            // Check if the character is a digit
13            if (isdigit(ch)) {
14                int digitValue = ch - '0'; // Convert char to int digit
15              
16                // If the digit is greater than the current highest digit
17                if (digitValue > highest) {
18                    secondHighest = highest; // Update second highest to the old highest
19                    highest = digitValue; // Update highest to the new digit
20                } // Check if the digit is between the highest and second highest
21                else if (digitValue > secondHighest && digitValue < highest) {
22                    secondHighest = digitValue; // Update the second highest
23                }
24            }
25        }
26        return secondHighest; // Return the second highest digit found
27    }
28};
29
1// Function to find the second highest digit in a given string.
2function secondHighest(s: string): number {
3    let highestDigit = -1;     // Initialize the highest digit as -1.
4    let secondHighestDigit = -1; // Initialize the second highest digit as -1.
5
6    // Iterate through each character in the string.
7    for (const character of s) {
8        // Check if the current character is a digit.
9        if (character >= '0' && character <= '9') {
10            // Convert the character to its corresponding numerical value.
11            const digit = character.charCodeAt(0) - '0'.charCodeAt(0);
12
13            // Check if we've found a new highest digit.
14            if (highestDigit < digit) {
15                // Update highest and second highest digits.
16                secondHighestDigit = highestDigit;
17                highestDigit = digit;
18            } else if (highestDigit !== digit && secondHighestDigit < digit) {
19                // Update the second highest digit if the digit is
20                // greater than the current second highest and not equal to the highest.
21                secondHighestDigit = digit;
22            }
23        }
24    }
25
26    // Return the second highest digit found in the string.
27    return secondHighestDigit;
28}
29
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

Time Complexity

The time complexity of the provided function is O(n), where n is the length of the input string s. This is because the function iterates over each character in the string exactly once. During each iteration, the operations performed (such as checking if the character is a digit, converting to an integer, comparing integer values, and assigning variables) are all constant time operations, hence they do not affect the overall linear complexity.

Space Complexity

The space complexity of the code is O(1), as the space used does not scale with the input size. Only a fixed number of integer variables a and b are used to store the highest and second highest digits found, regardless of the size of the string.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫