标签: 字符串
难度: Easy
给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数 ：
num 的一个长度为 3 的 子字符串 。3 次组成。以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。
注意：
num 或优质整数中可能存在 前导零 。示例 1：
输入：num = "6777133339" 输出："777" 解释：num 中存在两个优质整数："777" 和 "333" 。 "777" 是最大的那个，所以返回 "777" 。
示例 2：
输入：num = "2300019" 输出："000" 解释："000" 是唯一一个优质整数。
示例 3：
输入：num = "42352338" 输出："" 解释：不存在长度为 3 且仅由一个唯一数字组成的整数。因此，不存在优质整数。
提示：
3 <= num.length <= 1000num 仅由数字（0 - 9）组成运行时间: 28 ms
内存: 16.0 MB
class Solution:
def largestGoodInteger(self, num: str) -> str:
for i in range(9, -1, -1):
res = str(i) * 3
if res in num:
return res
return ""
该题解的思路是从最大的数字9开始，依次检查到最小的数字0，看是否存在由相同的一个数字连续重复三次组成的子字符串。一旦找到这样的子字符串，即返回它作为最大的优质整数。这种方法保证了找到的第一个匹配的三位数字是最大的，因为它从最大的数字开始检查。
时间复杂度: O(n)
空间复杂度: O(1)
# 定义Solution类
class Solution:
def largestGoodInteger(self, num: str) -> str:
# 从最大的数字9开始向下检查到0
for i in range(9, -1, -1):
# 创建一个由相同数字i连续重复三次组成的字符串
res = str(i) * 3
# 检查这个字符串是否为num的子字符串
if res in num:
return res # 找到则返回该字符串
return "" # 如果没有找到任何符合条件的子字符串，返回空字符串
在这个算法中，从9到0的遍历顺序是为了确保第一个找到的三位连续相同数字是最大的。因为数字9是所有数字中最大的，逐步向下检查到0可以保证我们立即返回的是最大的可行值，无需再进行额外的比较或存储。如果从0到9进行检查，则需要记录下每次发现的三个连续相同的数字，并在遍历结束后比较哪个是最大的，这显然增加了算法的复杂性和运行时间。
当输入字符串`num`非常长时，这种方法可能会表现出一定的性能瓶颈，因为对于每一个数字（从9到0），我们都需要在整个字符串中搜索一个长度为3的子字符串。这种搜索的时间复杂度为O(n)，其中n是字符串的长度。更优的搜索策略可以是一次遍历字符串，使用一个长度为3的滑动窗口来检查每一组连续的三个字符是否相同，并记录下遇到的最大数字。这种策略的时间复杂度仍然是O(n)，但它只需要遍历字符串一次，从而减少了重复的工作量。
在这种特定的算法实现中，边界情况自然地被处理了，因为我们是在搜索一个长度恰好为3的固定子字符串。当使用`in`关键字在Python中检查子字符串时，它会处理所有包括字符串开头和结尾的情况。例如，如果子字符串是字符串的前三个或最后三个字符，这种方法也能正确识别出来。因此，不需要特别处理这些边界情况。
根据题目要求和算法设计，我们只需要返回最大的三位连续相同数字，而不需要关心它在字符串中的位置或出现的次数。因此，一旦我们找到了第一个（也是最大的）匹配的三位数字，就没有必要继续搜索了。这是因为我们的搜索策略已经从最大的可能数值开始，向下进行，保证了首次找到的三位连续数字就是所求的最大值。