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.
字符串中最大的 3 位相同数字。
给你一个字符串 num ,表示一个大整数。如果一个整数满足下述所有条件,则认为该整数是一个 优质整数 :
该整数是 num 的一个长度为 3 的 子字符串 。
该整数由唯一一个数字重复 3 次组成。
以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数,则返回一个空字符串 "" 。
注意:
子字符串 是字符串中的一个连续字符序列。
num 或优质整数中可能存在 前导零 。
思路
从 index = 0 的位置开始截取一个长度为 3 的子串,看看这个子串是否满足三个字符都相同,不满足则接着往后看;如果是连续三个字符都相同,那么看一下这个子串形成的数字是否比之前记录的结果要大,以决定是否要更新结果。
复杂度
时间O(n)
空间O(1)
代码
Java实现
class Solution {
public String largestGoodInteger(String num) {
String res = "";
int n = num.length();
for (int i = 0; i + 2 < n; i++) {
if (num.charAt(i) == num.charAt(i + 1) && num.charAt(i) == num.charAt(i + 2)) {
String str = helper(num.charAt(i));
if (str.compareTo(res) > 0) {
res = str;
}
}
}
return res;
}
private String helper(char cur) {
StringBuilder sb = new StringBuilder();
sb.append(cur);
sb.append(cur);
sb.append(cur);
return sb.toString();
}
}
- Same-Digit LeetCode Largest Number Stringsame-digit leetcode largest number leetcode largest number string customer placing largest number leetcode largest labels values 倍数leetcode multiple largest bigdecimal string number java rearrangements submatrix leetcode largest leetcode number happy 202 f-string python string number leetcode croaking minimum number