Problem

Given an alphanumeric string s, return _thesecond 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.

Examples

Example 1

1
2
3

Input: s = "dfa12321afd"
Output: 2
Explanation: The digits that appear in s are [1, 2, 3]. The second largest digit is 2.

Example 2

1
2
3

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.

Solution

Method 1 - Set and Max Tracking

Intuition

We need to find the second largest digit in the string. We can collect all digits, sort or track the two largest, and return the second largest if it exists.

Approach

  1. Iterate through the string, collect all digits in a set.
  2. If there are fewer than 2 unique digits, return -1.
  3. Otherwise, return the second largest digit.

Code

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

#include <string>
#include <set>
using namespace std;
class Solution {
public:
    int secondHighest(string s) {
        set<int> digits;
        for (char c : s) if (isdigit(c)) digits.insert(c - '0');
        if (digits.size() < 2) return -1;
        auto it = digits.rbegin();
        ++it;
        return *it;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func secondHighest(s string) int {
    seen := [10]bool{}
    for _, c := range s {
        if c >= '0' && c <= '9' {
            seen[c-'0'] = true
        }
    }
    cnt := 0
    for i := 9; i >= 0; i-- {
        if seen[i] {
            cnt++
            if cnt == 2 {
                return i
            }
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import java.util.*;
class Solution {
    public int secondHighest(String s) {
        TreeSet<Integer> set = new TreeSet<>();
        for (char c : s.toCharArray())
            if (Character.isDigit(c)) set.add(c - '0');
        if (set.size() < 2) return -1;
        set.pollLast();
        return set.last();
    }
}
1
2
3
4
5
6
7

class Solution {
    fun secondHighest(s: String): Int {
        val set = sortedSetOf<Int>()
        for (c in s) if (c.isDigit()) set.add(c - '0')
        return if (set.size < 2) -1 else set.elementAt(set.size - 2)
    }
}
1
2
3
4
5

def secondHighest(s: str) -> int:
    digits = {int(c) for c in s if c.isdigit()}
    if len(digits) < 2:
        return -1
    return sorted(digits)[-2]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

use std::collections::BTreeSet;
pub fn second_highest(s: String) -> i32 {
    let mut set = BTreeSet::new();
    for c in s.chars() {
        if c.is_ascii_digit() {
            set.insert(c as u8 - b'0');
        }
    }
    if set.len() < 2 { return -1; }
    let mut v: Vec<_> = set.into_iter().collect();
    v[v.len()-2] as i32
}
1
2
3
4
5
6

function secondHighest(s: string): number {
    const digits = new Set<number>();
    for (const c of s) if (c >= '0' && c <= '9') digits.add(Number(c));
    if (digits.size < 2) return -1;
    return [...digits].sort((a, b) => a - b)[digits.size - 2];
}

Complexity

  • ⏰ Time complexity: O(n) (n = length of s)
  • 🧺 Space complexity: O(1) (at most 10 digits)