Largest 3-Same-Digit Number in String

Difficulty: Easy | Acceptance: 72.70% | Paid: No Topics: String

You are given a string num representing a large integer. An integer is good if it is a substring of num with length 3 and it consists of only one unique digit.

Return the maximum good integer as a string or an empty string if no such integer exists.

Note that a good integer occurs at most once in num.

• Examples
• Constraints
• Approach 1: Linear Scan
• Approach 2: Regular Expressions
• Approach 3: Grouping Consecutive Digits

Examples

Example 1:

Input: num = "6777133339"
Output: "777"
Explanation: There are two distinct good integers: "777" and "333".
"777" is the largest, so we return "777".

Example 2:

Input: num = "2300019"
Output: "000"
Explanation: "000" is the only good integer.

Example 3:

Input: num = "42352338"
Output: ""
Explanation: No good integer exists.

Constraints

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

Approach 1: Linear Scan

Intuition We iterate through the string once, checking every triplet of consecutive characters. If a triplet consists of the same digit, we compare it with the largest one found so far.

Steps

• Initialize a result string as empty.
• Iterate from index 0 to the third-to-last character.
• For each index i, check if num[i], num[i+1], and num[i+2] are equal.
• If they are equal, extract the substring and update the result if this substring is lexicographically larger.
• Return the result.

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        res = ""
        for i in range(len(num) - 2):
            if num[i] == num[i+1] == num[i+2]:
                sub = num[i:i+3]
                if sub > res:
                    res = sub
        return res

Complexity

• Time: O(n) where n is the length of the string.
• Space: O(1) as we only store a constant size result string.
• Notes: This is the most efficient approach for this problem.

Approach 2: Regular Expressions

Intuition We can use a regular expression to find all substrings that match the pattern of three identical consecutive digits. Then we simply find the maximum value among them.

Steps

• Define a regex pattern to match three consecutive identical digits.
• Find all matches in the input string.
• If matches exist, return the maximum value.
• Otherwise, return an empty string.

import re
class Solution:
    def largestGoodInteger(self, num: str) -> str:
        matches = re.findall(r"(d)\1\1", num)
        if not matches:
            return ""
        return max(matches) * 3

Complexity

• Time: O(n) for the regex engine to scan the string.
• Space: O(n) to store the matches (or O(1) if iterating directly).
• Notes: Regex is concise but often has higher constant overhead than a simple loop.

Approach 3: Grouping Consecutive Digits

Intuition We iterate through the string and count the length of consecutive runs of the same digit. If a run length is 3 or more, we check if that digit is the largest seen so far.

Steps

• Initialize max_digit to -1.
• Iterate through the string, counting consecutive identical digits.
• When the digit changes or the string ends, check if the run length was at least 3.
• If so, update max_digit if the current digit is larger.
• Finally, construct the result string by repeating max_digit three times, or return empty if max_digit is -1.

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        max_digit = -1
        count = 1
        for i in range(1, len(num)):
            if num[i] == num[i-1]:
                count += 1
            else:
                if count >= 3:
                    max_digit = max(max_digit, int(num[i-1]))
                count = 1
        if count >= 3:
            max_digit = max(max_digit, int(num[-1]))
        if max_digit == -1:
            return ""
        return str(max_digit) * 3

Complexity

• Time: O(n) as we traverse the string once.
• Space: O(1) extra space.
• Notes: This approach is useful if the problem required finding runs of length k instead of just 3.