algoadvance

Leetcode 830. Positions of Large Groups

Problem Statement

LeetCode Problem 830: Positions of Large Groups

In a string s of lowercase letters, a “large group” is a group where three or more consecutive characters are the same.

Write a function that finds the start and end positions of every large group. The function should return a list of lists of integers where each list denotes the starting and ending positions (inclusive) of each large group, in the order of their occurrence in the string.

Example:

Input: s = "abbxxxxzzy"
Output: [[3,6]]

Input: s = "abc"
Output: []

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]

Clarifying Questions

  1. Can the input string contain non-lowercase characters?
    • No, the input string consists only of lowercase letters.
  2. Are there any constraints on the length of the input string?
    • No specific constraints were given, but typically, interview problems handle strings of reasonable length that fit in memory.
  3. Do overlapping groups occur?
    • No, groups are strictly consecutive characters.

Strategy

  1. Initialize an empty list to store the positions of large groups.
  2. Use two pointers (i and j) to iterate through the string.
  3. Initialize i at 0. Move j until characters at i and j are the same.
  4. When characters differ or end of the string is reached, check the length of the group using the difference between j and i.
    • If the difference is 3 or more, record the start (i) and end (j-1) index of the group.
  5. Update i to be at j and continue the process until the end of the string is reached.
  6. Return the list of large groups.

Code

import java.util.ArrayList;
import java.util.List;

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

        while (i < n) {
            int j = i;

            // Move j until we find a different character
            while (j < n && s.charAt(j) == s.charAt(i)) {
                j++;
            }

            // If length of the group is 3 or more
            if (j - i >= 3) {
                List<Integer> group = new ArrayList<>();
                group.add(i);
                group.add(j - 1);
                result.add(group);
            }

            // Move i to j
            i = j;
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Test cases
        System.out.println(sol.largeGroupPositions("abbxxxxzzy")); // [[3, 6]]
        System.out.println(sol.largeGroupPositions("abc"));        // []
        System.out.println(sol.largeGroupPositions("abcdddeeeeaabbbcd")); // [[3,5],[6,9],[12,14]]
    }
}

Time Complexity

With this strategy and code, the positions of large groups can be efficiently determined.

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