Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 796c013

Browse filesBrowse files
2xiao2xiao
committed
add 5 solutions
1 parent 27cf110 commit 796c013
Copy full SHA for 796c013
Expand file treeCollapse file tree

27 files changed

+1306
-113
lines changed

‎assets/output/2981.md

Copy file name to clipboardExpand all lines: assets/output/2981.md
+245-51Lines changed: 245 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -33,41 +33,38 @@ thrice_.
3333
A **substring** is a contiguous **non-empty** sequence of characters within a
3434
string.
3535

36-
37-
3836
**Example 1:**
3937

4038
> Input: s = "aaaa"
41-
>
39+
>
4240
> Output: 2
43-
>
41+
>
4442
> Explanation: The longest special substring which occurs thrice is "aa": substrings "_**aa**_ aa", "a _**aa**_ a", and "aa _**aa**_ ".
45-
>
43+
>
4644
> It can be shown that the maximum length achievable is 2.
4745
4846
**Example 2:**
4947

5048
> Input: s = "abcdef"
51-
>
49+
>
5250
> Output: -1
53-
>
51+
>
5452
> Explanation: There exists no special substring which occurs at least thrice. Hence return -1.
5553
5654
**Example 3:**
5755

5856
> Input: s = "abcaba"
59-
>
57+
>
6058
> Output: 1
61-
>
59+
>
6260
> Explanation: The longest special substring which occurs thrice is "a": substrings "_**a**_ bcaba", "abc _**a**_ ba", and "abcab _**a**_ ".
63-
>
61+
>
6462
> It can be shown that the maximum length achievable is 1.
6563
6664
**Constraints:**
6765

68-
* `3 <= s.length <= 50`
69-
* `s` consists of only lowercase English letters.
70-
66+
- `3 <= s.length <= 50`
67+
- `s` consists of only lowercase English letters.
7168

7269
## 题目大意
7370

@@ -80,82 +77,279 @@ string.
8077

8178
**子字符串** 是字符串中的一个连续**非空** 字符序列。
8279

83-
84-
8580
**示例 1：**
8681

87-
>
88-
>
89-
>
90-
>
91-
>
9282
> **输入：** s = "aaaa"
93-
>
83+
>
9484
> **输出：** 2
95-
>
85+
>
9686
> **解释：** 出现三次的最长特殊子字符串是 "aa" ：子字符串 "_**aa**_ aa"、"a _**aa**_ a" 和 "aa _**aa**_ "。
97-
>
87+
>
9888
> 可以证明最大长度是 2 。
99-
>
100-
>
10189
10290
**示例 2：**
10391

104-
>
105-
>
106-
>
107-
>
108-
>
10992
> **输入：** s = "abcdef"
110-
>
93+
>
11194
> **输出：** -1
112-
>
95+
>
11396
> **解释：** 不存在出现至少三次的特殊子字符串。因此返回 -1 。
114-
>
115-
>
11697
11798
**示例 3：**
11899

119-
>
120-
>
121-
>
122-
>
123-
>
124100
> **输入：** s = "abcaba"
125-
>
101+
>
126102
> **输出：** 1
127-
>
103+
>
128104
> **解释：** 出现三次的最长特殊子字符串是 "a" ：子字符串 "_**a**_ bcaba"、"abc _**a**_ ba" 和 "abcab _**a**_ "。
129-
>
105+
>
130106
> 可以证明最大长度是 1 。
131-
>
132-
>
133107
108+
**提示：**
134109

110+
- `3 <= s.length <= 50`
111+
- `s` 仅由小写英文字母组成。
135112

136-
**提示：**
113+
## 解题思路
137114

138-
* `3 <= s.length <= 50`
139-
* `s` 仅由小写英文字母组成。
115+
### 思路一：暴力遍历
140116

117+
1. **遍历子串长度：**
118+
- 从最长可能的长度开始遍历，逐步检查是否存在符合条件的特殊子串。
119+
2. **检查特殊字符串：**
141120

142-
## 解题思路
121+
- 使用 `new Set(sub).size` 检查子串是否由单一字符组成。
122+
- 如果 `size === 1`，表示子串为特殊字符串。
123+
124+
3. **统计子串出现次数：**
125+
126+
- 利用 `Map` 数据结构记录每个特殊子串的出现次数。
127+
- 遍历完成后，检查是否有子串的出现次数达到 3 次以上。
128+
129+
4. **返回结果：**
130+
- 如果找到满足条件的子串，返回其长度。
131+
- 如果没有找到，返回 `-1`。
143132

144133
#### 复杂度分析
145134

146-
- **时间复杂度**：`O()`，
147-
- **空间复杂度**：`O()`，
135+
- **时间复杂度：** `O(n^3)`
136+
137+
- 外层循环遍历可能的子串长度，从最大值逐步减少，最多为 `O(n)`。
138+
- 内层遍历所有子串，最多为 `O(n^2)`。
139+
- 检查特殊字符串的过程为 `O(k)`，其中 `k` 为子串长度。
140+
- 总时间复杂度为 `O(n^3)`。
141+
142+
- **空间复杂度：** `O(n^2)`
143+
- 使用 `Map` 记录子串的出现次数，最差情况下存储所有子串，空间复杂度为 `O(n^2)`。
144+
145+
这段代码效率较低，对于较大输入可能会超时，可以进一步优化。
146+
147+
---
148+
149+
### 思路二：双指针
150+
151+
1. **定义判断函数 `isValid`**
152+
153+
用一个辅助函数 `isValid(len)` 检查是否存在长度为 `len` 的特殊子字符串，且该子字符串至少出现 3 次。
154+
155+
具体逻辑如下：
156+
157+
- 使用一个 `count` 数组，记录每个字符的特殊子字符串出现次数。
158+
- 使用双指针 `p, i`，维护子字符串的起始和结束位置：
159+
- 移动 `p` 直到 `s[i] === s[p]`，从而找到以 `s[i]` 为单一字符组成的连续子字符串的起点。
160+
- 如果当前子字符串长度 `i - p + 1 >= len`，说明可以把这段子字符串作为长度为 `len` 的特殊子字符串，增加计数。
161+
- 如果任意字符的计数达到 3，则返回 `true`，说明存在满足条件的子字符串。
162+
163+
2. **从大到小尝试长度**
164+
165+
由于我们要找的是最长的特殊子字符串长度，因此：
166+
167+
1. 从最大可能长度 `s.length - 2` 开始尝试，逐渐减小长度。
168+
2. 对于每一个长度 `len`，调用 `isValid(len)` 检查是否满足条件：
169+
170+
- 如果满足，直接返回 `len`。
171+
- 否则继续尝试更短的长度，直到 `len = 1`。
172+
173+
3. **终止条件**
174+
175+
如果遍历完所有长度都不满足，返回 `-1`。
176+
177+
#### 复杂度分析
178+
179+
- **时间复杂度：** `O(n^2)`
180+
181+
- 外层循环从最大长度到最小长度，最多进行 `O(n)` 次。
182+
- 内部 `isValid` 函数，双指针扫描整个字符串，每个字符最多访问两次，复杂度为 `O(n)`。
183+
- 总时间复杂度为 `O(n^2)`。
184+
185+
- **空间复杂度：** `O(1)`
186+
- 使用 `count` 数组记录每个字符的特殊子字符串出现次数，大小固定为 26，空间复杂度为 `O(1)`。
187+
- 其他变量占用常量空间。
188+
189+
---
190+
191+
### 思路三：二分查找 + 双指针
192+
193+
在思路二的基础上，我们可以使用二分查找确定最长特殊子字符串的长度：
194+
195+
- 初始范围为 `1` 到字符串长度 `s.length`。
196+
- 通过中点 `mid` 分割：
197+
- 如果长度为 `mid` 的特殊子字符串满足条件，则更新左边界 `left = mid - 1`。
198+
- 否则更新右边界 `right = mid + 1`。
199+
- 二分结束后，`right` 即为满足条件的最大长度，注意不是 `left`，因为在每次迭代中都排除了 `mid`，而 `mid` 本身也可以是答案之一。
200+
- 特殊情况处理：如果长度为 1 的特殊子字符串都不存在（即 `isValid(1)` 返回 `false`），直接返回 `-1`。
201+
202+
#### 复杂度分析
203+
204+
- **时间复杂度：** `O(n * log n)`
205+
206+
- 二分查找，复杂度为 `O(log n)` 。
207+
- 内部 `isValid` 函数，双指针扫描整个字符串，每个字符最多访问两次，复杂度为 `O(n)`。
208+
- 总时间复杂度为 `O(n * log n)`。
209+
210+
- **空间复杂度：** `O(1)`
211+
- 使用 `count` 数组记录每个字符的特殊子字符串出现次数，大小固定为 26，空间复杂度为 `O(1)`。
212+
- 其他变量占用常量空间。
148213

149214
## 代码
150215

216+
::: code-tabs
217+
218+
@tab 暴力遍历
219+
151220
```javascript
221+
/**
222+
* @param {string} s
223+
* @return {number}
224+
*/
225+
var maximumLength = function (s) {
226+
let minRange = 1,
227+
maxRange = s.length - 2;
228+
229+
for (let len = maxRange; len >= minRange; len--) {
230+
let map = new Map();
231+
232+
// 遍历所有长度为 len 的子串
233+
for (let j = 0; j <= s.length - len; j++) {
234+
let sub = s.substring(j, j + len);
235+
236+
// 检查子串是否是特殊字符串（由单一字符组成）
237+
if (new Set(sub).size === 1) {
238+
map.set(sub, (map.get(sub) || 0) + 1);
239+
}
240+
}
241+
242+
// 检查是否有子串出现至少 3 次
243+
for (let key of map.keys()) {
244+
if (map.get(key) >= 3) {
245+
return len;
246+
}
247+
}
248+
}
249+
250+
return -1;
251+
};
252+
```
253+
254+
@tab 双指针
152255

256+
```javascript
257+
/**
258+
* @param {string} s
259+
* @return {number}
260+
*/
261+
var maximumLength = function (s) {
262+
// 判断长度为 len 的特殊子字符串是否满足条件
263+
const isValid = (len) => {
264+
let count = new Array(26).fill(0);
265+
let p = 0;
266+
for (let i = 0; i < s.length; i++) {
267+
const char = s[i].charCodeAt() - 'a'.charCodeAt();
268+
// 移动指针 p，确保子字符串以单一字符组成
269+
while (s[i] !== s[p]) p++;
270+
// 如果当前子字符串长度 >= len，增加计数
271+
if (i - p + 1 >= len) {
272+
count[char]++;
273+
}
274+
// 如果出现至少 3 次，返回 true
275+
if (count[char] >= 3) {
276+
return true;
277+
}
278+
}
279+
// 未找到符合条件的子字符串
280+
return false;
281+
};
282+
283+
let minRange = 1,
284+
maxRange = s.length - 2;
285+
286+
// 从大到小尝试长度
287+
for (let len = maxRange; len >= minRange; len--) {
288+
if (isValid(len)) return len;
289+
}
290+
291+
// 如果没有找到，返回 -1
292+
return -1;
293+
};
294+
```
295+
296+
@tab 二分查找 + 双指针
297+
298+
```javascript
299+
/**
300+
* @param {string} s
301+
* @return {number}
302+
*/
303+
var maximumLength = function (s) {
304+
// 判断长度为 len 的特殊子字符串是否满足条件
305+
const isValid = (len) => {
306+
let count = new Array(26).fill(0);
307+
let p = 0;
308+
for (let i = 0; i < s.length; i++) {
309+
const char = s[i].charCodeAt() - 'a'.charCodeAt();
310+
// 移动指针 p，确保子字符串以单一字符组成
311+
while (s[i] !== s[p]) p++;
312+
// 如果当前子字符串长度 >= len，增加计数
313+
if (i - p + 1 >= len) {
314+
count[char]++;
315+
}
316+
// 如果出现至少 3 次，返回 true
317+
if (count[char] >= 3) {
318+
return true;
319+
}
320+
}
321+
// 未找到符合条件的子字符串
322+
return false;
323+
};
324+
325+
// 特殊情况处理：如果长度为 1 的特殊子字符串都不存在，直接返回 -1
326+
if (!isValid(1)) return -1;
327+
328+
// 二分查找
329+
let left = 1,
330+
right = s.length;
331+
332+
while (left <= right) {
333+
const mid = ((left + right) / 2) | 0;
334+
if (isValid(mid)) {
335+
// 更新左边界
336+
left = mid + 1;
337+
} else {
338+
// 更新右边界
339+
right = mid - 1;
340+
}
341+
}
342+
343+
return right;
344+
};
153345
```
154346

347+
:::
348+
155349
## 相关题目
156350

157351
<!-- prettier-ignore -->
158352
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
159353
| :------: | :------ | :------: | :------ | :------: | :------: |
160354
| 3 | 无重复字符的最长子串 | [[✓]](/problem/0003.md) | [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) [`滑动窗口`](/tag/sliding-window.md) | 🟠 | [🀄️](https://leetcode.cn/problems/longest-substring-without-repeating-characters) [🔗](https://leetcode.com/problems/longest-substring-without-repeating-characters) |
161-
| 395 | 至少有 K 个重复字符的最长子串 | | [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) [`分治`](/tag/divide-and-conquer.md) `1+` | 🟠 | [🀄️](https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters) [🔗](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters) |
355+
| 395 | 至少有 K 个重复字符的最长子串 | | [`哈希表`](/tag/hash-table.md) [`字符串`](/tag/string.md) [`分治`](/tag/divide-and-conquer.md) `1+` | 🟠 | [🀄️](https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters) [🔗](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters) |

‎src/.vuepress/public/.htaccess

Copy file name to clipboardExpand all lines: src/.vuepress/public/.htaccess
-13Lines changed: 0 additions & 13 deletions
This file was deleted.

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.