LeetCode 830. Positions of Large Groups

Description

https://leetcode.com/problems/positions-of-large-groups/

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.

Example 1:

Input: s = "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the only large group with start index 3 and end index 6.

Example 2:

Input: s = "abc"
Output: []
Explanation: We have groups "a", "b", and "c", none of which are large groups.

Example 3:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

Example 4:

Input: s = "aba"
Output: []

Constraints:

  • 1 <= s.length <= 1000
  • s contains lower-case English letters only.

Explanation

Iterate the list with two pointers. If the fast pointer is different than the slow pointer letter, move the slow to the fast position, and reset the consecutive count.

Python Solution

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        results = []
        
        i = 0        
        j = 0
        
        consecutive_count = 0
        
        while j < len(s):
            
            if s[j] != s[i]:
                if j - i > 2:
                    results.append([i, j - 1])
                i = j    
                consecutive_count = 1
            else:
                consecutive_count += 1
                
            j += 1

        if consecutive_count > 2:
            results.append([i, j - 1])
                
        return sorted(results, key=lambda result:result[0])
  • Time Complexity: O(Nlog(N)).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published. Required fields are marked *