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 <= 1000s contains lowercase English letters only
Hints for Positions of Large Groups
Hint 1
Walk the string once and notice where one run ends and the next begins.
Hint 2
Keep the index where the current run started; a run ends when the next character differs or the string ends.
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
- Set
i = 0. - While
i < n, advancejfromiwhiles[j] == s[i]; the run isi..j-1. - If
j - i >= 3, append[i, j - 1]. - 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 resJava
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