830. Positions of Large Groups
Easy
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".
Constraints:
1 <= s.length <= 1000
s
contains lowercase English letters only.
一開始的醜陋程式碼:
func largeGroupPositions(s string) [][]int {
start:=0
end:=0
ans := make([][]int, 0)
for i:=1; i<len(s); i++ {
if s[i] == s[i-1] {
end = i
} else {
if end-start >= 2 {
ans = append(ans, []int{start, end})
}
start = i
end = i
}
}
if end-start >= 2 {
ans = append(ans, []int{start, end})
}
return ans
}
後來發現 end = i-1 以及 如果把 s 後面再加上一個空格,就可以不需要最後的 if 。
改進過後的程式碼:
Runtime: 0 ms, faster than 100.00%
Memory Usage: 2.7 MB, less than 48.48%
func largeGroupPositions(s string) [][]int {
s = s+ " "
start:=0
ans := make([][]int, 0)
for i:=1; i<len(s); i++ {
if s[i] != s[i-1] {
if i-start >= 3 {
ans = append(ans, []int{start, i-1})
}
start = i
}
}
return ans
}