# Second Largest Digit in a String
**Difficulty:** EASY
[External](https://leetcode.com/problems/second-largest-digit-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/second-largest-digit-in-a-string
**Data structures:** Hash Table, String
**Companies:** [Softwire](https://scaleengineer.com/companies/softwire)
---
## Problem
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.

# Approaches
## Brute Force with Sorting
This approach involves extracting all the numerical digits from the string, storing them in a list, sorting the list, and then finding the second largest unique digit.
**Time:** O(K log K), where K is the number of digits in the string `s`. In the worst case, the entire string consists of digits, making the complexity O(N log N), where N is the length of the string. Sorting the list of digits dominates the time complexity. · **Space:** O(K), where K is the number of digits. In the worst case, this is O(N), as we need to store all digits in a list.
**Pros:** Relatively straightforward to conceptualize and implement.
**Cons:** Inefficient in both time and space, especially for strings with many digits.; Requires extra logic to handle duplicate digits after sorting.
### Explanation
The core idea is to collect every digit, sort them, and then find the second unique largest value from the end of the sorted list. This is a straightforward but inefficient method due to storing and sorting all digits, including duplicates.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int secondHighest(String s) {
        List<Integer> digits = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                digits.add(c - '0');
            }
        }

        if (digits.isEmpty()) {
            return -1;
        }

        Collections.sort(digits);

        int largest = digits.get(digits.size() - 1);
        for (int i = digits.size() - 2; i >= 0; i--) {
            if (digits.get(i) < largest) {
                return digits.get(i);
            }
        }

        return -1; // All digits were the same
    }
}
```
### Algorithm
- Create an empty list of integers, say `digits`.
- Iterate through each character of the input string `s`.
- If the character is a digit, convert it to an integer and add it to the `digits` list.
- After populating the list, sort it in ascending order.
- Find the largest element, which is the last one in the sorted list.
- Iterate backwards from the second-to-last element. The first element that is strictly less than the largest element is the second largest digit.
- If no such element is found (meaning all digits were the same), return -1. Otherwise, return the found digit.

## Using a Set to Store Unique Digits
A more optimized approach is to use a `HashSet` to store only the unique digits encountered. This avoids storing duplicates and simplifies finding the second largest element.
**Time:** O(N), where N is the length of the string. Iterating through the string takes O(N). Adding to a `HashSet` takes O(1) on average. The number of unique digits is at most 10, so converting the set to a list and sorting it takes constant time. Thus, the overall complexity is dominated by the initial string traversal. · **Space:** O(1). The `HashSet` will store at most 10 unique digits (0-9), so the space required is constant.
**Pros:** Time and space efficient.; The use of a `Set` elegantly handles duplicate digits.
**Cons:** Involves overhead from creating data structures (`Set`, `List`) and calling a sort function, which can be slightly slower in practice than a single-pass approach.
### Explanation
This approach improves upon the brute-force method by using a `HashSet` to automatically handle duplicate digits. This simplifies the logic and improves performance as the number of unique digits is small and constant (at most 10).

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public int secondHighest(String s) {
        Set<Integer> uniqueDigits = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                uniqueDigits.add(c - '0');
            }
        }

        if (uniqueDigits.size() < 2) {
            return -1;
        }

        List<Integer> sortedDigits = new ArrayList<>(uniqueDigits);
        Collections.sort(sortedDigits);

        return sortedDigits.get(sortedDigits.size() - 2);
    }
}
```
### Algorithm
- Initialize an empty `HashSet` of integers to store unique digits.
- Iterate through each character of the input string `s`.
- If the character is a digit, convert it to an integer and add it to the `HashSet`.
- After the iteration, check the size of the set. If it's less than 2, return -1.
- Convert the `HashSet` to a `List` and sort it in ascending order.
- The second largest digit is now at the second-to-last index of the sorted list. Return this value.

## Single Pass Approach
The most efficient method is to find the two largest unique digits in a single pass through the string, using only two variables to track the largest and second largest digits found so far.
**Time:** O(N), where N is the length of the string. We perform a single pass over the string. · **Space:** O(1). We only use a few variables to store the state, regardless of the input string size.
**Pros:** Optimal time and space complexity.; Fastest practical solution due to low overhead and a single loop without extra data structures.
**Cons:** The logic can be slightly more complex to write correctly compared to the `Set`-based approach.
### Explanation
This is the most optimal approach. It finds the result by iterating through the string just once, keeping track of the two largest unique digits seen so far without using any extra data structures. This avoids the overhead of collections and sorting, resulting in the best performance.

```java
class Solution {
    public int secondHighest(String s) {
        int firstMax = -1;
        int secondMax = -1;

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                int digit = c - '0';
                if (digit > firstMax) {
                    secondMax = firstMax;
                    firstMax = digit;
                } else if (digit < firstMax && digit > secondMax) {
                    secondMax = digit;
                }
            }
        }
        return secondMax;
    }
}
```
### Algorithm
- Initialize two integer variables, `firstMax` and `secondMax`, to -1.
- Iterate through each character of the input string `s`.
- If the character is a digit, convert it to its integer value, `digit`.
- Compare `digit` with `firstMax` and `secondMax`:
  - If `digit > firstMax`: Update `secondMax = firstMax` and `firstMax = digit`.
  - Else if `digit < firstMax` and `digit > secondMax`: Update `secondMax = digit`.
- After the loop, return `secondMax`.

# Solutions
### Java

```java
class Solution {
public
  int secondHighest(String s) {
    int a = -1, b = -1;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (Character.isDigit(c)) {
        int v = c - '0';
        if (v > a) {
          b = a;
          a = v;
        } else if (v > b && v < a) {
          b = v;
        }
      }
    }
    return b;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int secondHighest(string s) {
    int a = -1, b = -1;
    for (char &c : s) {
      if (isdigit(c)) {
        int v = c - '0';
        if (v > a) {
          b = a, a = v;
        } else if (v > b && v < a) {
          b = v;
        }
      }
    }
    return b;
  }
};

```

### Python

```python
class Solution:
    def secondHighest(self, s: str) -> int: a = b = - 1 for c in s: if c . isdigit(): v = int(c) if v > a: a, b = v, a elif b < v < a: b = v return b

```