Title: Positions of Large Groups Source: leetcode.com
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”.
Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.
The final answer should be in lexicographic order.
Example 1:
Input: “abbxxxxzzy”
Output: [[3,6]]
Explanation: “xxxx” is the single large group with starting 3 and ending positions 6.
Example 2:
Input: “abc”
Output: []
Explanation: We have “a”,”b” and “c” but no large group.
Example 3:
Input: “abcdddeeeeaabbbcd”
Output: [[3,5],[6,9],[12,14]]
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
''' https://leetcode.com/problems/positions-of-large-groups/ ''' class Solution(object): def largeGroupPositions(self, S): """ :type S: str :rtype: List[List[int]] """ ln = len(S) i = 1 cur_idx = [0,0] cur_chr = S[0] output = [] while i < ln: if cur_chr == S[i]: cur_idx[1] = i else: cur_chr = S[i] if cur_idx[1] - cur_idx[0] >= 2: output.append(cur_idx) cur_idx = [i, i] i += 1 if cur_idx[1] - cur_idx[0] >= 2: output.append(cur_idx) return output |