Easy

题目描述

给你一个字符串 num，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 好整数 ：

  • 它是 num 的一个长度为 3 的 子字符串。
  • 它由唯一的一个数字组成。

返回 最大的好整数 作为 字符串，如果不存在满足条件的整数，则返回一个空字符串 ""。

注意：

  • 子字符串 是字符串中连续的字符序列。
  • num 或好整数中可能有 前导零。

示例 1：

输入：num = "6777133339"
输出："777"
解释：num 中存在两个不同的好整数："777" 和 "333" 。
"777" 是最大的，所以返回 "777" 。

示例 2：

输入：num = "2300019"
输出："000"
解释："000" 是唯一的好整数。

示例 3：

输入：num = "42352338"
输出：""
解释：不存在长度为 3 且由唯一数字组成的子字符串。因此，不存在好整数。

提示：

  • 3 <= num.length <= 1000
  • num 只由数字组成。

解题思路

这道题要求找到字符串中最大的3位相同数字。我们需要找到所有由相同数字组成的长度为3的子字符串，然后返回其中最大的一个。

有两种主要解法：

解法一：贪心法（推荐） 由于题目要求最大的好整数，我们可以按照从大到小的顺序检查 “999”、“888”、“777”、…、“000” 是否在字符串中出现。第一个找到的就是答案，这样可以保证结果是最大的。

解法二：遍历法 遍历整个字符串，检查每个长度为3的子字符串是否由相同数字组成。记录所有满足条件的子字符串，然后返回其中最大的一个。

贪心法更高效，因为一旦找到就可以立即返回，避免了不必要的遍历。而遍历法需要检查所有可能的子字符串。

两种方法的时间复杂度都不错，但贪心法在实际执行中通常更快，特别是当最大的好整数比较大时。

代码实现

class Solution {
public:
    string largestGoodInteger(string num) {
        // 从最大的开始检查
        for (char digit = '9'; digit >= '0'; digit--) {
            string target(3, digit);
            if (num.find(target) != string::npos) {
                return target;
            }
        }
        return "";
    }
};

class Solution:
    def largestGoodInteger(self, num: str) -> str:
        # 从最大的开始检查
        for digit in '9876543210':
            target = digit * 3
            if target in num:
                return target
        return ""

public class Solution {
    public string LargestGoodInteger(string num) {
        // 从最大的开始检查
        for (char digit = '9'; digit >= '0'; digit--) {
            string target = new string(digit, 3);
            if (num.Contains(target)) {
                return target;
            }
        }
        return "";
    }
}

var largestGoodInteger = function(num) {
    // 从最大的开始检查
    for (let digit = 9; digit >= 0; digit--) {
        const target = digit.toString().repeat(3);
        if (num.includes(target)) {
            return target;
        }
    }
    return "";
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)最坏情况下需要检查10个可能的好整数，每次检查需要O(n)时间
空间复杂度O(1)只使用了常数额外空间

相关题目