Skip to content

2264. Largest 3-Same-Digit Number in String

Description

You are given a string num representing a large integer. An integer is good if it meets the following conditions:

  • It is a substring of num with length 3.
  • 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:

  • A substring is a contiguous sequence of characters within a string.
  • There may be leading zeroes in num or a good integer.

 

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

Solutions

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

If we have enumerated all the possible values of \(i\) and still haven't found a substring that satisfies the condition, we return an empty string.

The time complexity is \(O(10 \times n)\), where \(n\) is the length of the string \(num\). The space complexity is \(O(1)\).

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 ""

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public String largestGoodInteger(String num) {
        for (int i = 9; i >= 0; i--) {
            String s = String.valueOf(i).repeat(3);
            if (num.contains(s)) {
                return s;
            }
        }
        return "";
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    string largestGoodInteger(string num) {
        for (char i = '9'; i >= '0'; --i) {
            string s(3, i);
            if (num.find(s) != string::npos) {
                return s;
            }
        }
        return "";
    }
};

1
2
3
4
5
6
7
8
func largestGoodInteger(num string) string {
    for c := '9'; c >= '0'; c-- {
        if s := strings.Repeat(string(c), 3); strings.Contains(num, s) {
            return s
        }
    }
    return ""
}

1
2
3
4
5
6
7
8
9
function largestGoodInteger(num: string): string {
    for (let i = 9; i >= 0; i--) {
        const s = String(i).repeat(3);
        if (num.includes(s)) {
            return s;
        }
    }
    return '';
}

Comments