[LeetCode] 每日一题 2264. 字符串中最大的 3 位相同数字

题目链接

https://leetcode.cn/problems/largest-3-same-digit-number-in-string

题目描述

给你一个字符串 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 <= 1000

• num 仅由数字（0 - 9）组成

题解

解题思路

1. 遍历字符串
   使用滑动窗口思想，从字符串的第 2 位开始遍历，检查当前字符与前两位字符是否相同，判断是否为优质整数

2. 记录最大值
   如果找到一个优质整数，将其数值部分与当前最大值比较，更新记录的最大值

3. 返回结果
   遍历完成后，根据记录的最大值，返回对应的优质整数。如果没有找到，返回空字符串

代码实现

class Solution {
    public String largestGoodInteger(String num) {
        int max = -1; // 初始化最大值为 -1 表示尚未找到优质整数
        String ans = ""; // 用于记录最大优质整数

        for (int i = 2; i < num.length(); i++) {
            // 判断当前字符是否与前两个字符相同
            if (num.charAt(i) == num.charAt(i - 1) && num.charAt(i) == num.charAt(i - 2)) {
                int current = num.charAt(i) - '0';
                // 如果当前数值更大，则更新最大值和答案
                if (current > max) {
                    max = current;
                    ans = num.substring(i - 2, i + 1);
                }
            }
        }
        return ans;
    }
}

复杂度分析

1. 时间复杂度

   • 遍历整个字符串时，每次检查一个长度为 3 的子字符串。假设字符串长度为 n，时间复杂度为 O(n)

2. 空间复杂度

   • 只使用了常数空间来记录最大值和结果字符串，因此空间复杂度为 O(1)

总结

这道题考查了对字符串操作的基本功和滑动窗口的应用。解题过程中需要特别注意以下几点：

1. 连续字符判断
   使用简单的条件判断即可完成，同时注意字符转数值时减去 '0'

2. 处理前导零
   本题无需额外处理前导零，因为子字符串的比较基于数值

3. 边界条件
   如果字符串长度小于 3，直接返回空字符串

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。