题目地址：

https://www.lintcode.com/problem/twitch-words/description

给定一个字符串$s$，求其只包含相同字母且长度大于$3$的所有子串的起始终点位置。按照从左到右的顺序返回。

遍历$s$，如果发现$s[i]=s[i+1]$，则新开一个指针从$i+1$出发遍历所有与$s[i]$相等的字符，如果截出来的长度大于等于$3$则将起始终点下标加入答案。代码如下：

import java.util.ArrayList; import java.util.List; public class Solution { /** * @param str: the origin string * @return: the start and end of every twitch words */ public int[][] twitchWords(String str) { // Write your code here List<int[]> list = new ArrayList<>(); for (int i = 0; i < str.length() - 1; i++) { char ch = str.charAt(i); if (ch == str.charAt(i + 1)) { int j = i + 1; while (j < str.length() && str.charAt(j) == ch) { j++; } if (j - i >= 3) { list.add(new int[]{i, j - 1}); } // 有i++，所以将i挪到j前面一格 i = j - 1; } } int[][] res = new int[list.size()][2]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; } }

时空复杂度$O(n)$。