830. 较大分组的位置

🟢 🔖 字符串 🔗 力扣open in new window LeetCodeopen in new window

题目

In a string s of lowercase letters, these letters form consecutive groups of the same character.

For example, a string like s = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z", and "yy".

A group is identified by an interval [start, end], where start and end denote the start and end indices (inclusive) of the group. In the above example, "xxxx" has the interval [3,6].

A group is considered large if it has 3 or more characters.

Return the intervals of every large group sorted in increasing order by start index.

Example 1:

Input: s = "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the only large group with start index 3 and end index 6.

Example 2:

Input: s = "abc"
Output: []
Explanation: We have groups "a", "b", and "c", none of which are large groups.

Example 3:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

Constraints:

1 <= s.length <= 1000
s contains lowercase English letters only.

题目大意

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后 ，返回结果。

示例 1：

输入： s = "abbxxxxzzy"
输出：[[3,6]]
解释： "xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入： s = "abc"
输出：[]
解释： "a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入： s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释： 较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入： s = "aba"
输出：[]

提示：

1 <= s.length <= 1000
s 仅含小写英文字母

解题思路

可以通过一次遍历字符串，记录连续字符的起点和终点，当字符发生变化时判断这段连续字符的长度是否大于等于 3，从而找到大组。

初始化变量：
- start 表示当前连续字符的起始位置。
- 遍历字符串时，用 end 表示当前字符的位置。
- 使用结果数组 res 存储所有大组的起始和结束位置。
遍历字符串：
- 如果当前字符 s[end] 与前一个字符 s[start] 不同：
  - 检查从 start 到 end - 1 的字符数量是否大于等于 3：
    - 如果是，将 [start, end - 1] 添加到结果数组。
  - 将 start 更新为 end，即新一段连续字符的起始位置。
处理最后一组字符：
- 如果字符串结尾的最后一组字符长度大于等于 3，将其位置添加到结果数组。
返回结果：
- 返回存储大组位置的数组 res。

复杂度分析

时间复杂度：O(n)，其中 n 是字符串的长度，遍历字符串一次。
空间复杂度：O(n)，结果数组 res 存储所有大组的位置，最坏情况下，所有字符形成一个大组。

代码

/**
 * @param {string} s
 * @return {number[][]}
 */
var largeGroupPositions = function (s) {
	const n = s.length;
	let res = [];
	let start = 0;

	// 遍历字符串
	for (let end = 0; end < n; end++) {
		// 当字符变化时，处理当前段
		if (s[end] !== s[start]) {
			if (end - start > 2) {
				res.push([start, end - 1]);
			}
			start = end; // 更新起始位置
		}
	}

	// 处理最后一组字符
	if (n - start > 2) {
		res.push([start, n - 1]);
	}

	return res;
};

830. 较大分组的位置

# 830. 较大分组的位置

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

830. 较大分组的位置

题目

题目大意

解题思路

复杂度分析

代码

相关题目