#2264

Easy

auto_awesomeString-driven solution strategy

LeetCode Problem Workspace

Largest 3-Same-Digit Number in String

Find the largest 3-same-digit number within a string of digits using a string-driven solution approach.

Problem Statement

You are given a string num representing a large integer. An integer is considered good if it consists of three consecutive digits that are the same. Your task is to find the largest such good integer, or return an empty string if no such integer exists.

To solve this, you will need to check for all potential 3-digit sequences from '999' down to '000' within the string num. The first sequence that matches is the largest valid good integer.

Examples

Example 1

Input: num = "6777133339"

Output: "777"

There are two distinct good integers: "777" and "333". "777" is the largest, so we return "777".

Example 2

Input: num = "2300019"

Output: "000"

"000" is the only good integer.

Example 3

Input: num = "42352338"

Output: ""

No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

Constraints

3 <= num.length <= 1000
num only consists of digits.

Solution Approach

Start with the largest possible good integer

Begin by checking if '999' exists in the string. Then proceed sequentially down through '888', '777', ..., '000'. This ensures that the first match you find will be the largest possible good integer.

Efficiently check for each sequence

For each candidate good integer (from '999' to '000'), simply check if the sequence exists within the string using built-in string functions. This guarantees an optimal time complexity of O(n).

Return the result or empty string

If a good integer is found, return it immediately. If no match is found after checking all possibilities, return an empty string as the result.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because we only need to check for the presence of each 3-digit sequence in the string, where n is the length of the string. The space complexity is O(1) since no additional space is needed beyond the constant variables used to check for sequences.

What Interviewers Usually Probe

Look for understanding of string manipulation and optimization in checking sequences.
Evaluate the candidate's ability to leverage built-in functions for efficiency.
Check if they correctly handle edge cases, such as strings with no valid good integers.

Common Pitfalls or Variants

Common pitfalls

Failing to check for the sequences in the correct order, leading to inefficient or incorrect results.
Not handling strings with no valid good integers correctly, potentially returning incorrect results.
Misunderstanding the problem's constraints and overcomplicating the solution.

Follow-up variants

What if the string contains more than one valid good integer? The problem only requires returning the largest one.
What if the string has repeated 3-digit sequences? Ensure to return the first largest found.
What if the string contains only one or two digits? The output should be an empty string as no valid good integer can exist.

FAQ

What is the largest 3-same-digit number in string "6777133339"?

"777" is the largest 3-same-digit number in the string.

How do I approach the "Largest 3-Same-Digit Number in String" problem efficiently?

Start by checking for '999', '888', '777', and so on, in that order, to find the first match, ensuring efficiency.

What happens if no good integer is found in the string?

If no valid 3-same-digit number exists, return an empty string.

Can I find multiple good integers in a string?

Yes, but only the largest 3-same-digit number should be returned.

What is the time complexity of the "Largest 3-Same-Digit Number in String" problem?

The time complexity is O(n), where n is the length of the string.

terminal

Solution

Solution 1: Enumeration

We can enumerate each digit $i$ from large to small, where $0 \le i \le 9$, and then check whether the string $s$ consisting of three consecutive $i$ is a substring of $num$. If it is, we directly return $s$.

1

2

3

4

5

6

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        for i in range(9, -1, -1):
            if (s := str(i) * 3) in num:
                return s
        return ""

Continue Practicing

#2262 total appeal of a string #2266 count number of texts #2259 remove digit from number to maximize result