1796. Second Largest Digit in a String

Description

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.

Solutions

Solution 1: One Pass

We define \(a\) and \(b\) to represent the largest and second largest numbers in the string, initially \(a = b = -1\).

We traverse the string \(s\). If the current character is a digit, we convert it to a number \(v\). If \(v > a\), it means that \(v\) is the largest number currently appearing, we update \(b\) to \(a\), and update \(a\) to \(v\); if \(v < a\), it means that \(v\) is the second largest number currently appearing, we update \(b\) to \(v\).

After the traversal, we return \(b\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScriptRustC

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

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;
    }
}

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;
    }
};

func secondHighest(s string) int {
    a, b := -1, -1
    for _, c := range s {
        if c >= '0' && c <= '9' {
            v := int(c - '0')
            if v > a {
                b, a = a, v
            } else if v > b && v < a {
                b = v
            }
        }
    }
    return b
}

function secondHighest(s: string): number {
    let first = -1;
    let second = -1;
    for (const c of s) {
        if (c >= '0' && c <= '9') {
            const num = c.charCodeAt(0) - '0'.charCodeAt(0);
            if (first < num) {
                [first, second] = [num, first];
            } else if (first !== num && second < num) {
                second = num;
            }
        }
    }
    return second;
}

impl Solution {
    pub fn second_highest(s: String) -> i32 {
        let mut first = -1;
        let mut second = -1;
        for c in s.as_bytes() {
            if char::is_digit(*c as char, 10) {
                let num = (c - b'0') as i32;
                if first < num {
                    second = first;
                    first = num;
                } else if num < first && second < num {
                    second = num;
                }
            }
        }
        second
    }
}

int secondHighest(char* s) {
    int first = -1;
    int second = -1;
    for (int i = 0; s[i]; i++) {
        if (isdigit(s[i])) {
            int num = s[i] - '0';
            if (num > first) {
                second = first;
                first = num;
            } else if (num < first && second < num) {
                second = num;
            }
        }
    }
    return second;
}

Solution 2: Bit Manipulation

We can use an integer \(mask\) to mark the numbers that appear in the string, where the \(i\)-th bit of \(mask\) indicates whether the number \(i\) has appeared.

We traverse the string \(s\). If the current character is a digit, we convert it to a number \(v\), and set the \(v\)-th bit of \(mask\) to \(1\).

Finally, we traverse \(mask\) from high to low, find the second bit that is \(1\), and the corresponding number is the second largest number. If there is no second largest number, return \(-1\).

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). The space complexity is \(O(1)\).

Python3JavaC++Go

class Solution:
    def secondHighest(self, s: str) -> int:
        mask = reduce(or_, (1 << int(c) for c in s if c.isdigit()), 0)
        cnt = 0
        for i in range(9, -1, -1):
            if (mask >> i) & 1:
                cnt += 1
            if cnt == 2:
                return i
        return -1

class Solution {
    public int secondHighest(String s) {
        int mask = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                mask |= 1 << (c - '0');
            }
        }
        for (int i = 9, cnt = 0; i >= 0; --i) {
            if (((mask >> i) & 1) == 1 && ++cnt == 2) {
                return i;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int secondHighest(string s) {
        int mask = 0;
        for (char& c : s)
            if (isdigit(c)) mask |= 1 << c - '0';
        for (int i = 9, cnt = 0; ~i; --i)
            if (mask >> i & 1 && ++cnt == 2) return i;
        return -1;
    }
};

func secondHighest(s string) int {
    mask := 0
    for _, c := range s {
        if c >= '0' && c <= '9' {
            mask |= 1 << int(c-'0')
        }
    }
    for i, cnt := 9, 0; i >= 0; i-- {
        if mask>>i&1 == 1 {
            cnt++
            if cnt == 2 {
                return i
            }
        }
    }
    return -1
}

Comments