Сложность: easy
В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.
Верните интервалы каждой большой группы, отсортированные в порядке возрастания начального индекса.
Пример:
Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".
👨💻 Алгоритм:
1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.
2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.
3⃣Обновите i = j + 1 и начните новую группу.
😎 Решение:
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<int>> largeGroupPositions(string S) {
vector<vector<int>> ans;
int i = 0, N = S.size();
for (int j = 0; j < N; ++j) {
if (j == N - 1 || S[j] != S[j + 1]) {
if (j - i + 1 >= 3) {
ans.push_back({i, j});
}
i = j + 1;
}
}
return ans;
}
};
Ставь 👍 и забирай 📚 Базу знаний