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 <= 1000scontains 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 counter.
Python Solution
class Solution:
def largeGroupPositions(self, s: str) -> List[List[int]]:
results = []
i = 0
j = 0
visited = set()
while j < len(s):
if len(visited) == 0:
visited.add(s[j])
j += 1
elif s[j] not in visited:
if j - i > 2:
results.append([i, j - 1])
visited = set()
i = j
else:
j += 1
if len(visited) > 0 and j - i > 2:
results.append([i, j - 1])
return results- Time Complexity: O(Nlog(N)).
- Space Complexity: O(N).