Positions of Large Groups

Easy
1174.

Positions of Large Groups

Positions of Large Groups is an easy coding problem on strings and two pointers, asked in Google and Adobe interviews.

The string s is made of lowercase letters. A group is a maximal run of equal consecutive characters — in "kaaairooo" the groups are "k", "aaa", "i", "r" and "ooo".

A group is large when it holds three or more characters. Describe each large group by the pair [start, end] of the indices of its first and last characters (0-indexed, both inclusive).

Return the pairs of every large group, ordered by start ascending. Return an empty list if there are none.

Example 1

Input
s = "kaaairooo"
Output
[[1,3],[6,8]]
Explanation
`"aaa"` covers indices 1..3 and `"ooo"` covers 6..8.

Example 2

Input
s = "codekairo"
Output
[]
Explanation
Every group has length 1.

Example 3

Input
s = "zzzzz"
Output
[[0,4]]

Constraints

  • 1 <= s.length <= 1000
  • s contains lowercase English letters only
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number[][]}
 */
var largeGroupPositions = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Positions of Large Groups — Solution in Python, Java & C++

Positions of Large Groups solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Positions of Large Groups is an easy coding problem on strings and two pointers, asked in Google and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Two Pointers
  • Asked at: Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The string s is made of lowercase letters. A group is a maximal run of equal consecutive characters — in "kaaairooo" the groups are "k", "aaa", "i", "r" and "ooo".

A group is large when it holds three or more characters. Describe each large group by the pair [start, end] of the indices of its first and last characters (0-indexed, both inclusive).

Return the pairs of every large group, ordered by start ascending. Return an empty list if there are none.

Example 1

Input: s = "kaaairooo"
Output: [[1,3],[6,8]]
Explanation: `"aaa"` covers indices 1..3 and `"ooo"` covers 6..8.

Example 2

Input: s = "codekairo"
Output: []
Explanation: Every group has length 1.

Example 3

Input: s = "zzzzz"
Output: [[0,4]]

Constraints

  • 1 <= s.length <= 1000
  • s contains lowercase English letters only

Hints for Positions of Large Groups

  1. Hint 1

    Walk the string once and notice where one run ends and the next begins.

  2. Hint 2

    Keep the index where the current run started; a run ends when the next character differs or the string ends.

  3. Hint 3

    At each run end, if end - start + 1 >= 3, record [start, end] — runs are found left to right, so the list is already sorted.

How to solve Positions of Large Groups

Groups are just runs of equal characters, so one left-to-right scan with a run-start pointer finds every group, and the long ones are recorded as they close.

Approach

  1. Set i = 0.
  2. While i < n, advance j from i while s[j] == s[i]; the run is i..j-1.
  3. If j - i >= 3, append [i, j - 1].
  4. Continue from i = j.

Why it works

Every index belongs to exactly one run, and the scan visits runs in order of their start, so each large group is reported exactly once and the output comes out sorted without any extra work.

Complexity

  • Time — O(n)
  • Space — O(1) besides the output

Pitfalls

  • The last run ends at the end of the string, not at a character change — make sure it is checked too.
  • The end index is inclusive: a run of length 3 starting at 4 is [4,6], not [4,7].
  • A run of exactly three characters already counts as large.

Reference solution

Python

from typing import List

def largeGroupPositions(s: str) -> List[List[int]]:
    res = []
    n = len(s)
    i = 0
    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

Java

public static int[][] largeGroupPositions(String s) {
    List<int[]> 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(new int[] { i, j - 1 });
        i = j;
    }
    return res.toArray(new int[0][]);
}

C++

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;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Two Pointers Technique