Positions of Large Groups Problem & Solution

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.

See the positions of large groups problem on LeetCode.

C++ Solution

#pragma GCC optimize("Ofast")
#pragma GCC optimization("fast-math")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")

static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

class Solution {
public:
  vector<vector<int>> largeGroupPositions(string s) {
    vector<vector<int>> result;

    int i = 0;
    for (int j = 1; j <= s.size(); ++j) {
      if (j == s.size() || s[i] != s[j]) {
        i = j;
      }

      if (j - i >= 2) {
        if (result.size() > 0 &&
            result.back()[0] == i) {
          result.back()[1] = j;
        } else {
          result.push_back({i, j});
        }
      }
    }

    return result;
  }
};

Sample Search Queries

Many Paths. Follow Yours.