Welcome to Subscribe On Youtube

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

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

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

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

• 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
  
  

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

All Problems

All Solutions