Positions of Large Groups - Practice Coding Problems

Positions of Large Groups - Problem

String Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: s = "abbxxxxzyy"

› Output: [[3,6]]

💡 Note: The groups are "a" (length 1), "bb" (length 2), "xxxx" (length 4), "z" (length 1), "yy" (length 2). Only "xxxx" has length ≥ 3, spanning indices [3,6].

Example 2 — Multiple Large Groups

$ Input: s = "abcdddeeeeaabbbcd"

› Output: [[3,5],[6,9],[12,14]]

💡 Note: Groups: "a"(1), "b"(1), "c"(1), "ddd"(3), "eeee"(4), "aa"(2), "bbb"(3), "c"(1), "d"(1). Large groups are "ddd" [3,5], "eeee" [6,9], "bbb" [12,14].

Example 3 — No Large Groups

$ Input: s = "abc"

› Output: []

💡 Note: All groups have length 1, which is less than 3, so no large groups exist.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

String with consecutive character groups

Find Groups

Identify consecutive same characters and their lengths

Filter Large

Return intervals of groups with length ≥ 3

Key Takeaway

🎯 Key Insight: Track group boundaries by detecting character changes in a single pass

Asked in

G Google 12 f Facebook 8

The key insight is to scan the string once while tracking consecutive groups. Best approach uses single pass scanning to identify when characters change and check if the previous group was large (≥3 characters). Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Scan	O(n)	O(1)	Scan string once, tracking current group start and length
Brute Force - Check All Substrings	O(n²)	O(1)	Check every possible substring to find large groups

Single Pass Scan — Algorithm Steps

Initialize group start at position 0
Scan through string character by character
When character changes or string ends, check if group length ≥ 3
If large, add [start, end] to result and start new group

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Current Group

Keep track of start position and scan forward

Detect Change

When character changes, check if previous group was large

Record Large Groups

Add qualifying groups to result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(char* s, int result[][2], int* resultSize) {
    *resultSize = 0;
    if (strlen(s) == 0) return;
    
    int start = 0;
    int n = strlen(s);
    
    for (int i = 1; i <= n; i++) {
        // Check if we reached end or character changed
        if (i == n || s[i] != s[start]) {
            // Check if current group is large
            if (i - start >= 3) {
                result[*resultSize][0] = start;
                result[*resultSize][1] = i - 1;
                (*resultSize)++;
            }
            start = i;
        }
    }
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    
    int result[100][2];
    int resultSize;
    
    solution(s, result, &resultSize);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d]", result[i][0], result[i][1]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string of length n

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current group, result array doesn't count

✓ Linear Space

15.4K Views

Medium Frequency

~15 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Scan — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler