Finding the Second Largest Digit in a String

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/or digits.

First of all, get the distinct characters since we are only interested in those
Let’s note that there might not be any digits.

Second Largest Digit in a String

The set in C++ has keys sorted (Internally implemented using Red-Black Tree). We then push all the digits to the set, and return the second largest using prev(prev(end())) if the size of the set is larger than 1.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int secondHighest(string s) {
        set<int> data;
        for (auto &n: s) {
            if (isdigit(n)) { //  if (n >= '0' && n <= '9') {
                data.insert(n - 48);
            }
        }
        if (data.size() <= 1) return -1;
        return *prev(prev(end(data)));
    }
};

class Solution {
public:
    int secondHighest(string s) {
        set<int> data;
        for (auto &n: s) {
            if (isdigit(n)) { //  if (n >= '0' && n <= '9') {
                data.insert(n - 48);
            }
        }
        if (data.size() <= 1) return -1;
        return *prev(prev(end(data)));
    }
};

In Python, we can convert a set to a list and then make it sorted before we get the second largest element in the set.

1
2
3
4
5
6
7
8
9

class Solution:
    def secondHighest(self, s: str) -> int:
        c = set()
        for i in s:
            if i.isdigit():
                c.add(i)
        if len(c) <= 1:
            return -1
        return sorted(list(c))[-2]

class Solution:
    def secondHighest(self, s: str) -> int:
        c = set()
        for i in s:
            if i.isdigit():
                c.add(i)
        if len(c) <= 1:
            return -1
        return sorted(list(c))[-2]

The time complexity for both implementations are O(N) where N is the number of the characters in the given string. And the space complexity is O(1) becauase we need using a set to store all the digits – which at most has 10 possibilities in this particular case.

–EOF (The Ultimate Computing & Technology Blog) —