Problem 1796

Abstract / Summary

Find the second highest different digit that appears in the given string of characters.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1796.py

class Solution:
    def secondHighest(self, s: str) -> int:
        digits = set()
        for c in s:
            if "0" <= c <= "9":
                digits.add(int(c))
        return sorted(digits)[-2] if len(digits) >= 2 else -1
7 lines | 239 bytes | submitted December 10, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 55% (200k+ submissions).

Typical patterns to solve this problem:
  • Hash Table
  • String
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a Solution class with a single method secondHighest. The method receives a string, extracts all numeric characters, and returns the second largest distinct digit found in the string. If fewer than two distinct digits exist, the method returns -1. The algorithm is concise, leverages Python’s built-in data structures, and operates directly on the input without auxiliary preprocessing.

Key Steps

The core logic can be broken down into three conceptual stages: collection, conversion, and selection. Each stage is illustrated with the corresponding fragment of the original source.

Collection of Digits

The method begins by creating an empty set named digits. A set is chosen because it automatically discards duplicate values, ensuring that each digit is stored only once.

digits = set()

Scanning and Filtering

A for loop iterates over every character c in the input string s. The conditional expression "0" <= c <= "9" checks whether the character falls within the ASCII range for decimal digits. When the condition holds, the character is converted to an integer and added to the digits set.

for c in s:
    if "0" <= c <= "9":
        digits.add(int(c))

Determining the Second Highest Value

After the scan completes, the set contains all distinct numeric characters present in the string. The set is transformed into a sorted list, which orders the digits in ascending order. The expression sorted(digits)[-2] accesses the element positioned second from the end, i.e., the second largest digit. A ternary conditional guards this operation: if the set holds at least two elements, the second highest digit is returned; otherwise, -1 signals the absence of a qualifying value.

return sorted(digits)[-2] if len(digits) >= 2 else -1

Edge Cases Handled

The implementation gracefully addresses several boundary conditions without additional code. When the input string contains no numeric characters, the digits set remains empty; the length check fails, and the method returns -1. If the string includes exactly one distinct digit-regardless of how many times it appears-the length condition again fails, yielding -1. Repeated occurrences of the same digit are collapsed by the set, preventing false positives for a second highest value. Non-digit characters, including letters, symbols, and whitespace, are ignored by the range check, ensuring they never affect the result. Leading zeros are treated as the integer 0, which participates correctly in the ordering logic; for example, a string "a0b0c" still yields -1 because only one distinct digit exists.

Performance Optimizations

The algorithm exploits the limited domain of possible digits (0-9) to keep work minimal. By storing digits in a set, the code eliminates duplicate processing early, reducing the size of the collection that later requires sorting. Since the maximum cardinality of the set is ten, the subsequent sorted call operates on a tiny, bounded list, making the sorting step effectively constant-time in practice. Leveraging Python’s built-in comparison operators for the range check ("0" <= c <= "9") avoids the overhead of regular expression matching or explicit conversion attempts, resulting in a fast, linear scan of the input string. The overall flow processes each character exactly once, and the use of native data structures ensures that the interpreter can apply highly optimized C-level implementations for set insertion and sorting.

written by openai gpt

ELI5 - Simplified Explanation

Imagine there is a big basket that starts out completely empty. A tiny robot looks at every single letter and number inside a long line of text. When the robot sees a digit like one, two, or three, it picks it up and puts it into the basket. The basket is special because it only allows one of each number, so if the robot finds two fives, it only keeps one of them. Once the robot looks at every single character in the message, it lines all the numbers it found up in order from the smallest to the largest, just like building a tall tower with blocks. After the tower is built, it looks for the second block from the top and holds that one up to show everyone. If there are not enough blocks in the tower to find a second one from the top, it lets everyone know that it could not find a winner.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 8 | μ = 7.56 | σ = 0.96

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java C Go Rust TS
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
DimitrisJim C
fartem Ruby
fsq C++
haoel C++
JoshCrozier JS
lkwq007 Python
suxrobGM C#
varunu28 Java
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C, C++, Go, Java, Python, Rust, TypeScript
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
fartem Ruby
fsq C++
haoel C++
JoshCrozier JavaScript
lkwq007 Python
suxrobGM C#
varunu28 Java
YuriSpiridonov Python
28 links | 15 authors | 10 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

1 similar problem

Solved On The Same Day

6 solutions   December 10, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality