Leetcode – Second Largest Digit in a String Solution

Spread the love

The ‘Second Largest Digit in a String’ problem on Leetcode is an engaging problem that tests one’s ability to manipulate and analyze strings in Python. This problem provides an excellent opportunity to explore the various approaches to solving string manipulation challenges. In this comprehensive article, we will take a look at the problem statement, walk through multiple approaches for solving it, and evaluate their respective time and space complexities.

Problem Statement

Given an alphanumeric string s, you need to find the second largest numerical digit that appears in s. If it does not exist, return -1.

Examples

Input: s = "dfa12321afd"
Output: 2

Input: s = "abc1111"
Output: -1

Approach 1: Simple Iteration and Sorting

One straightforward way to approach this problem is by iterating through the string to extract all the numerical digits, converting them to integers, storing them in a list, sorting the list, and finding the second largest number.

Algorithm Steps:

  1. Initialize an empty list called digits.
  2. Loop through each character in the string.
  3. If the character is a digit, add it to digits.
  4. Sort digits in ascending order.
  5. Return the second largest digit if it exists, otherwise return -1.

Python Code:

def secondHighest(s: str) -> int:
    digits = []
    for char in s:
        if char.isdigit():
            digits.append(int(char))
    digits = sorted(set(digits))
    return digits[-2] if len(digits) > 1 else -1

Time and Space Complexity

  • Time Complexity: O(n log⁡ n), primarily due to sorting.
  • Space Complexity: O(n), to store the list of digits.

Approach 2: Using Set and Iteration

We can optimize the above approach by using a set data structure. By adding the digits to a set, we inherently eliminate duplicate digits and keep the set sorted.

Algorithm Steps:

  1. Initialize an empty set called unique_digits.
  2. Loop through each character in the string.
  3. If the character is a digit, add it to unique_digits.
  4. Convert the set to a sorted list.
  5. Return the second largest digit if it exists, otherwise return -1.

Python Code:

def secondHighest(s: str) -> int:
    unique_digits = set()
    for char in s:
        if char.isdigit():
            unique_digits.add(int(char))
    unique_digits = sorted(unique_digits)
    return unique_digits[-2] if len(unique_digits) > 1 else -1

Time and Space Complexity

  • Time Complexity: O(n), as sets in Python are generally O(1) for add and search operations.
  • Space Complexity: O(n), to store the set of unique digits.

Approach 3: Using Max and Second Max Variables

We can further optimize this by tracking the largest and second-largest digits while we iterate through the string. This eliminates the need for any additional data structure.

Algorithm Steps:

  1. Initialize two variables max_digit and second_max_digit as -1.
  2. Loop through each character in the string.
  3. If the character is a digit and greater than max_digit, update second_max_digit and max_digit.
  4. If the digit is between max_digit and second_max_digit, update second_max_digit.
  5. Return second_max_digit.

Python Code:

def secondHighest(s: str) -> int:
    max_digit = second_max_digit = -1
    for char in s:
        if char.isdigit():
            digit = int(char)
            if digit > max_digit:
                second_max_digit = max_digit
                max_digit = digit
            elif digit < max_digit:
                second_max_digit = max(second_max_digit, digit)
    return second_max_digit

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(1), as we are using only constant extra space.

Conclusion

The ‘Second Largest Digit in a String’ problem is a fascinating problem that allows us to explore multiple ways of solving the same issue. It is an excellent problem to understand the nuances of string manipulation, data structures like lists and sets, and keeping track of variables while iterating through a list.

Leave a Reply