Leetcode 830 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”.

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]]

Note: 1 <= S.length <= 1000

思路：
一道简单的字符串处理问题。每次判断是否有连续三个以上的字符相同，相同则将下标加入res。注意处理边界问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def largeGroupPositions(S):
    """
    :type S: str
    :rtype: List[List[int]]
    """
    i,j = 0,0
    res = []
    while i < len(S):
        j = i+1
        while j < len(S) and S[j] == S[i]: j+=1
        if j-i >= 3: res.append([i,j-1])
        i = j
    return res

"difficulty: easy
202 / 202 test cases passed.
Runtime: 114 ms"