原文链接: https://leetcode-cn.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.

中文题目

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

 

示例 1：

输入：s = "abbxxxxzzy"
输出：[[3,6]]
解释："xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入：s = "abc"
输出：[]
解释："a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入：s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入：s = "aba"
输出：[]

 

提示：

• 1 <= s.length <= 1000
• s 仅含小写英文字母

通过代码

高赞题解

一 正则

([a-z])捕获小写字母，\1反向引用刚才捕获的字母，{2,}该字母又出现>=2次
matchAll

var largeGroupPositions = function(s) {
    let g = s.matchAll(/([a-z])\1{2,}/g), r = [], t
    while (t = g.next().value) r.push([t.index, t.index + t[0].length - 1])
    return r
};

matchAll · 1行代码

var largeGroupPositions = function(s) {
    return Array.from(s.matchAll(/(.)\1\1+/g), v => [v.index, v.index + v[0].length - 1])
};

replace：.匹配除换行符以外的任意字符

var largeGroupPositions = function(s) {
    const r = []
    s.replace(/(.)\1{2,}/g, (a, _, i)=> r.push([i, i + a.length - 1]))
    return r
};

二 扫描

start不同字母首次出现索引，初始0。遍历遇下个不同字母，更新start
字母

var largeGroupPositions = function(s) {
    let i = 0, start = 0, r = []
    while (++i <= s.length) // = 时，JS数组越界不报错，处理类似 aaa 情况
        if (s[start] !== s[i]) {
            if (i - start > 2) r.push([start, i - 1])
            start = i
        }
    return r
};

位运算 · 异或：字母转Unicode编码，相同^为0

var largeGroupPositions = function(s) {
    let i = 0, start = 0, r = []
    while (++i <= s.length) 
        if (s.charCodeAt(start) ^ s.charCodeAt(i)) {
            if (i - start > 2) r.push([start, i - 1])
            start = i
        }
    return r
};

Proxy：拦截数组push方法，不满足连续出现次数>=3不真正push

var largeGroupPositions = function(s) {
    let i = 0, start = 0, r = [], p = proxy(r)
    while (++i <= s.length) 
        if (s[start] !== s[i]) {
            p.push([start, i - 1])
            start = i
        }
    return r
};
const proxy = r => new Proxy(r, {
    set (t, p, v) {         
        if (typeof v === 'object' && v[1] - v[0] > 1) t[p] = v
        return true
    }
})

三 位

小写字母转Unicode编码-97，范围[0, 25]。二进制的32位从左到右[1, 26]位可表示[a, z]

class Bit { // 构造Bit类，模仿Set，当Set用
    constructor () {
        this.clear()
    }
    add (v) { // 遇 a 转97，再-97 = 0，1左移0位 = 1。或 运算，占第1位
        this.bit |= 1 << v
        return this
    }
    has (v) { // 再遇 a，同上，1左移0位 = 1。且 运算，第1位已被占，找到连续 a
        return this.bit & 1 << v
    }
    clear () {
        this.bit = 0
        return this
    }
}

构造Bit类，遇不同字母(has返回0)，清空Bit并放入。相当于用!Bit.has代替上解法的!==

var largeGroupPositions = function(s) {
    let i = 0, start = 0, b = new Bit, r = [], t
    b.add(s.charCodeAt(0) - 97)
    while (++i < s.length) {
        if (!b.has(t = s.charCodeAt(i) - 97)) {
            if (i - start > 2) r.push([start, i - 1])
            start = i
            b.clear().add(t)
        }
    }
    if (i - start > 2) r.push([start, i - 1])
    return r
};

提示

Bit作用与Set一致，即判断字母是否重复出现。只是!Set.has字母不如直接!==快

var largeGroupPositions = function(s) {
    let i = 0, start = 0, b = new Set(s[0]), r = [], t
    while (++i <= s.length) 
        if (!b.has(s[i])) {
            if (i - start > 2) r.push([start, i - 1])
            start = i
            b.clear()
            b.add(s[i])
        }
    return r
};

四 栈

构造特殊栈：push时，遇不同元素，清空栈 并 返回清空前的长度，该长度即相同元素个数

class Stack {
    constructor () {
        this.q = []
    } 
    length () {
        return this.q.length
    }
    top () {
        return this.q[this.length() - 1]
    }
    clear () {
        this.q.length = 0
    }
    push (v) {
        let len = 0
        if (v !== this.top()) {
            len = this.length()
            this.clear()
        }
        this.q.push(v)
        return len
    }
}

遍历将元素放入栈，找 相同元素个数>=3 即可

var largeGroupPositions = function(s) {
    let i = -1, q = new Stack, r = []
    while (++i <= s.length) {
        const n = q.push(s[i])
        if (n > 2) r.push([i - n, i - 1])
    }
    return r
};

五 滑动窗口

来自@Xu-Quan Lyu

var largeGroupPositions = function(s) {
    let l = r = 0, n = s.length, res = []
    while (l < n) {
        while (r + 1 < n && s[r] === s[r + 1]) r++
        if (r - l > 1) res.push([l, r])
        l = ++r
    }
    return res
};

排行

长度1000随机小写字母，每种解法求解100次，每秒操作数

统计信息

通过次数	提交次数	AC比率
52638	96947	54.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言