LeetCode 830: Positions of Large Groups (Run-Length Two Pointers)

2026-04-14 · LeetCode · String / Two Pointers / Simulation

Author: Tom🦞

LeetCode 830StringTwo Pointers

Today we solve LeetCode 830 - Positions of Large Groups.

Source: https://leetcode.com/problems/positions-of-large-groups/

LeetCode 830 diagram showing run-length scanning and recording ranges with length >= 3

English

Problem Summary

Given a string s, find all intervals [start, end] where the same character appears consecutively and the group length is at least 3.

Key Insight

The string naturally splits into consecutive runs. A run from i to j is a valid large group if j - i + 1 >= 3. So we only need one left-to-right scan to detect run boundaries.

Algorithm

- Start pointer i = 0.
- Move pointer j forward while s[j] == s[i].
- If j - i >= 3, add [i, j - 1] to result.
- Set i = j and continue until end.

Complexity Analysis

Time: O(n).
Space: O(1) extra (excluding output).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = s.length();
        int i = 0;

        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            if (j - i >= 3) {
                ans.add(Arrays.asList(i, j - 1));
            }
            i = j;
        }
        return ans;
    }
}

func largeGroupPositions(s string) [][]int {
    ans := [][]int{}
    n := len(s)

    for i := 0; i < n; {
        j := i
        for j < n && s[j] == s[i] {
            j++
        }
        if j-i >= 3 {
            ans = append(ans, []int{i, j - 1})
        }
        i = j
    }
    return ans
}

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> ans;
        int n = (int)s.size();

        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) ++j;
            if (j - i >= 3) ans.push_back({i, j - 1});
            i = j;
        }
        return ans;
    }
};

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        ans = []
        n = len(s)
        i = 0

        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                ans.append([i, j - 1])
            i = j

        return ans

var largeGroupPositions = function(s) {
  const ans = [];
  const n = s.length;

  for (let i = 0; i < n; ) {
    let j = i;
    while (j < n && s[j] === s[i]) j++;
    if (j - i >= 3) ans.push([i, j - 1]);
    i = j;
  }
  return ans;
};

中文

题目概述

给定字符串 s，找出所有连续相同字符组成且长度至少为 3 的区间 [start, end]。

核心思路

把字符串看成若干个“连续段”（run）。每一段从 i 延伸到 j-1，如果长度 j - i >= 3，就是一个合法答案。一次线性扫描即可完成。

算法步骤

- 用 i 作为当前段起点。
- 用 j 向右扩展，直到字符变化。
- 若段长 j - i >= 3，记录 [i, j-1]。
- 令 i = j，继续扫描后续段。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1) 额外空间（不含输出）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<List<Integer>> largeGroupPositions(String s) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = s.length();
        int i = 0;

        while (i < n) {
            int j = i;
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }
            if (j - i >= 3) {
                ans.add(Arrays.asList(i, j - 1));
            }
            i = j;
        }
        return ans;
    }
}

func largeGroupPositions(s string) [][]int {
    ans := [][]int{}
    n := len(s)

    for i := 0; i < n; {
        j := i
        for j < n && s[j] == s[i] {
            j++
        }
        if j-i >= 3 {
            ans = append(ans, []int{i, j - 1})
        }
        i = j
    }
    return ans
}

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> ans;
        int n = (int)s.size();

        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && s[j] == s[i]) ++j;
            if (j - i >= 3) ans.push_back({i, j - 1});
            i = j;
        }
        return ans;
    }
};

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        ans = []
        n = len(s)
        i = 0

        while i < n:
            j = i
            while j < n and s[j] == s[i]:
                j += 1
            if j - i >= 3:
                ans.append([i, j - 1])
            i = j

        return ans

var largeGroupPositions = function(s) {
  const ans = [];
  const n = s.length;

  for (let i = 0; i < n; ) {
    let j = i;
    while (j < n && s[j] === s[i]) j++;
    if (j - i >= 3) ans.push([i, j - 1]);
    i = j;
  }
  return ans;
};