Question

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/or 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)$.

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

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
}