830. Positions of Large Groups

leetcode

#csharp#intervals#leetcode#sort#string

Task

: 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".

C# solution

matched/original

using System.Collections.Generic;
public class Solution {
    public IList<IList<int>> LargeGroupPositions(string S) {
        var ans = new List<IList<int>>();
        int i = 0, N = S.Length;
        for (int j = 0; j < N; ++j) {
            if (j == N - 1 || S[j] != S[j + 1]) {
                if (j - i + 1 >= 3) {
                    ans.Add(new List<int> { i, j });
                }
                i = j + 1;
            }
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public IList<vector<int>> LargeGroupPositions(string S) {
        var ans = new List<vector<int>>();
        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(new List<int> { i, j });
                }
                i = j + 1;
            }
        }
        return ans;
    }
}

Java solution

matched/original

class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> ans = new ArrayList();
        int i = 0, N = S.length();
        for (int j = 0; j < N; ++j) {
            if (j == N-1 || S.charAt(j) != S.charAt(j+1)) {
                if (j-i+1 >= 3)
                    ans.add(Arrays.asList(new Integer[]{i, j}));
                i = j + 1;
            }
        }

        return ans;
    }

Python solution

matched/original

class Solution:
    def largeGroupPositions(self, S: str):
        ans = []
        i, N = 0, len(S)

        for j in range(N):
            if j == N - 1 or S[j] != S[j + 1]:
                if j - i + 1 >= 3:
                    ans.append([i, j])
                i = j + 1

Go solution

matched/original

func largeGroupPositions(S string) [][]int {
    var ans [][]int
    i, N := 0, len(S)

    for j := 0; j < N; j++ {
        if j == N-1 || S[j] != S[j+1] {
            if j-i+1 >= 3 {
                ans = append(ans, []int{i, j})
            }
            i = j + 1
        }
    }

    return ans
}

Explanation

Algorithm

Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.

Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.

Обновите i = j + 1 и начните новую группу.

😎