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
numwith length3. - 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
numor 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 <= 1000numonly 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 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 6 7 8 9 | |