830. Positions of Large Groups(Leetcode每日一题-2021.01.05)

本文主要是介绍830. Positions of Large Groups(Leetcode每日一题-2021.01.05)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

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.

Constraints:

1 <= s.length <= 1000
s contains lower-case English letters only.

Example1

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

Example2

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

Example3

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

Example4

Input: s = “aba”
Output: []

Solution

class Solution {
public:vector<vector<int>> largeGroupPositions(string s) {vector<vector<int>> ret;if(s.empty())return ret;int cur_start = 0;int cur_end = 0;for(int i = 1;i<s.length();++i){if(i && s[i] == s[i-1]){++cur_end;}else{int len = cur_end - cur_start +1;vector<int> tmp;tmp.push_back(cur_start);tmp.push_back(cur_end);if(len >= 3){ret.push_back(tmp);}cur_start = i;cur_end = i;}}int len = cur_end - cur_start +1;vector<int> tmp;tmp.push_back(cur_start);tmp.push_back(cur_end);if(len >= 3){ret.push_back(tmp);}return ret;}
};