Skip to content

2264. Largest 3-Same-Digit Number in String

SourceWeekly Contest 292 Q1DifficultyEasyRating1308

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

Thinking

We want the largest three-equal-digit substring of \(\textit{num}\). The length is \(10^3\), so testing \(999,\ldots,000\) from large to small finds the maximum as soon as one occurs.

For \(i\) from \(9\) down to \(0\), check whether \(\texttt{str}(i)*3\) is a substring; otherwise return empty.

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 \(\textit{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(10n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the string \(\textit{num}\).

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