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:

- Initialize an empty list called
`digits`

. - Loop through each character in the string.
- If the character is a digit, add it to
`digits`

. - Sort
`digits`

in ascending order. - 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:

- Initialize an empty set called
`unique_digits`

. - Loop through each character in the string.
- If the character is a digit, add it to
`unique_digits`

. - Convert the set to a sorted list.
- 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:

- Initialize two variables
`max_digit`

and`second_max_digit`

as`-1`

. - Loop through each character in the string.
- If the character is a digit and greater than
`max_digit`

, update`second_max_digit`

and`max_digit`

. - If the digit is between
`max_digit`

and`second_max_digit`

, update`second_max_digit`

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