algoadvance

Leetcode 830. Positions of Large Groups

Problem Statement

The problem is as follows:

In a string s of lowercase letters, a “large group” is a group that has 3 or more consecutive identical characters.

Write a function largeGroupPositions that takes the string s as input and returns the starting and ending positions of every large group in the string. The positions should be returned as a list of lists where each list contains two integers [start, end].

Example:

Input: s = "abbxxxxzzy"
Output: [[3, 6]]
Explanation: "xxxx" is the only large group with starting and ending positions [3, 6].

Input: s = "abc"
Output: []
Explanation: There are no large groups in the string.

Constraints:

Clarifying Questions

  1. What should be returned if there are no large groups in the string?
    • An empty list should be returned.
  2. Are overlapping large groups possible?
    • No, as large groups consist of consecutive identical characters, overlapping is not possible.
  3. Do we need to handle edge cases for input constraints (minimum and maximum lengths)?
    • Yes, the function should work for the smallest input (length 1) and the largest (length 1000).

Strategy

  1. Iteration and Count: We will iterate through the string and count consecutive identical characters.
  2. Check Length: When current character != next character, we check if the count of consecutive characters is 3 or more.
  3. Record Positions: If the count is 3 or more, we store the starting and ending indices.
  4. Reset Counter: Reset the counter for the next new character sequence and continue.
  5. Edge Cases: Handle edge cases like strings shorter than 3 where large groups are not possible, and strings where all characters are the same.

Code

Here’s a possible implementation in C++:

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<int>> largeGroupPositions(string s) {
        vector<vector<int>> result;
        int n = s.size();
        int i = 0; // Initialize the starting pointer

        while (i < n) {
            int j = i;
            // Move j to the end of the current group of same characters
            while (j < n && s[j] == s[i]) {
                j++;
            }
            // If the length of this group is 3 or more, add to result
            if (j - i >= 3) {
                result.push_back({i, j - 1});
            }
            // Move i to the next new character
            i = j;
        }

        return result;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the length of the string. Each character in the string is processed once, and operations inside the loop are constant time operations.

Example Execution

For s = "abbxxxxzzy", this implementation would produce the output [[3, 6]]:

  1. i = 0: s[0] != s[1], so j = 1. Move i to 1.
  2. i = 1: s[1] == s[2] != s[3], j = 3, i to 3.
  3. i = 3: s[3] == s[4] == s[5] == s[6] != s[7], j = 7, large group xxxx from 3 to 6, add [3, 6] to result, i to 7.
  4. Process continues for the rest of the string.

If something is unclear or an edge case is missing, feel free to ask for further clarifications!

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI