Сложность: 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 и начните новую группу.
😎 Решение:
class Solution {
/**
* @param String $S
* @return Integer[][]
*/
function largeGroupPositions($S) {
$ans = [];
$i = 0;
$N = strlen($S);
for ($j = 0; $j < $N; ++$j) {
if ($j == $N - 1 || $S[$j] != $S[$j + 1]) {
if ($j - $i + 1 >= 3) {
$ans[] = [$i, $j];
}
$i = $j + 1;
}
}
return $ans;
}
}Ставь 👍 и забирай 📚 Базу знаний