Positions of Large Groups

easy string two-pointers

Problem

In a string s of lowercase letters, a 'large group' is a contiguous run of the same character with length at least 3. Return [start, end] for each such group, sorted by start index.

Inputs = "abbxxxxzzy"

Output[[3,6]]

Only "xxxx" (indices 3 to 6) has length >= 3.

s (lowercase letters)

def largeGroupPositions(s):
    res = []
    i = 0
    n = len(s)
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        if j - i >= 3:
            res.append([i, j - 1])
        i = j
    return res

function largeGroupPositions(s) {
  const res = [];
  const n = s.length;
  let i = 0;
  while (i < n) {
    let j = i;
    while (j < n && s[j] === s[i]) j++;
    if (j - i >= 3) res.push([i, j - 1]);
    i = j;
  }
  return res;
}

import java.util.*;
class Solution {
  public List<List<Integer>> largeGroupPositions(String s) {
    List<List<Integer>> res = new ArrayList<>();
    int n = s.length(), i = 0;
    while (i < n) {
      int j = i;
      while (j < n && s.charAt(j) == s.charAt(i)) j++;
      if (j - i >= 3) res.add(Arrays.asList(i, j - 1));
      i = j;
    }
    return res;
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> res;
        int n = s.size(), i = 0;
        while (i < n) {
            int j = i;
            while (j < n && s[j] == s[i]) j++;
            if (j - i >= 3) res.push_back({i, j - 1});
            i = j;
        }
        return res;
    }
};

Explanation

A "large group" is just a run of the same character repeated 3 or more times. The natural way to find runs is to scan the string and, whenever a run starts, jump straight to where it ends.

We use two pointers: i marks the start of a run, and an inner j races forward while s[j] == s[i]. When j stops, the run covers indices i through j - 1, so its length is j - i.

If that length is at least 3, we record [i, j - 1]. Either way, we set i = j so the next run begins exactly where this one ended — no index is visited twice.

Because every character is passed over only once by j, the whole scan is linear time, and groups come out already sorted by start index.

Example: s = "abbxxxxzzy". The runs are "a" (len 1), "bb" (len 2), "xxxx" (len 4), "zz" (len 2), "y" (len 1). Only "xxxx" qualifies, giving [[3, 6]].

Time: O(n) Space: O(1)