2264. 字符串中最大的 3 位相同数字

🟢   🔖  字符串  🔗 力扣 LeetCode

题目

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 = "6** 777** 133339"

Output: "777"

Explanation: There are two distinct good integers: "777" and "333".

"777" is the largest, so we return "777".

Example 2:

Input: num = "23**000** 19"

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.

题目大意

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

• 该整数是 num 的一个长度为 3 的 子字符串 。
• 该整数由唯一一个数字重复 3 次组成。

以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。

注意：

• 子字符串 是字符串中的一个连续字符序列。
• num 或优质整数中可能存在 前导零 。

示例 1：

输入： num = "6 777 133339"

输出： "777"

解释： num 中存在两个优质整数："777" 和 "333" 。

"777" 是最大的那个，所以返回 "777" 。

示例 2：

输入： num = "23 000 19"

输出： "000"

解释： "000" 是唯一一个优质整数。

示例 3：

输入： num = "42352338"

输出： ""

解释： 不存在长度为 3 且仅由一个唯一数字组成的整数。因此，不存在优质整数。

提示：

• 3 <= num.length <= 1000
• num 仅由数字（0 - 9）组成

解题思路

1. 滑动窗口思想：

   • 用两个指针（left 和 i）来标记连续相同数字的范围。
   • 如果当前数字与左指针指向的数字相同，则继续移动右指针 i。
   • 当数字不再相同时，检查当前范围的长度是否大于等于 3。

2. 更新结果：

   • 如果当前范围的长度 (i - left) 大于等于 3，并且 num[left] 比当前结果大，则更新结果为 num[left]。

3. 返回结果：

   • 如果存在 "Good Integer"，返回其值重复 3 次。
   • 如果不存在，返回空字符串。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度，遍历字符串一次
• 空间复杂度：O(1)，使用常量级额外空间。

代码

/**
 * @param {string} num
 * @return {string}
 */
var largestGoodInteger = function (num) {
	let left = 0,
		res = '';
	for (let i = 0; i < num.length; i++) {
		// 找到当前数字范围
		while (num[i] == num[left]) {
			i++;
		}
		// 检查范围是否满足条件
		if (i - left >= 3 && num[left] > res) {
			res = num[left];
		}
		left = i; // 更新左指针
	}
	return res.repeat(3); // 如果没有匹配，res 为 ""，返回 ""
};

相关题目

题号	标题	题解	标签	难度	力扣
1903	字符串中的最大奇数	[✓]	贪心 数学 字符串	🟢	🀄️ 🔗