无重复字符的最长子串 #
题目 #
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
```
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
```
示例 2:
```
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
```
示例 3:
```
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
```
Given a string, find the length of the longest substring without repeating characters.
Example 1:
```
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```
Example 2:
```
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
```
Example 3:
```
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
```
分析 #
举个例子
`yabcdedfayghciajkc`
- 当出现第二个 `a` 时,`bcdedfa` 就是无重复最长字串
- 当出现第二个 `y` 时,最长字串不是 `abcdedfay`,因为包括了两个 `a`
- 所以,`start` 是第一个 `y` 和 `start` (此时是第一个 `a`)中取大的
- 即 `bcdedfay`
题解 #
---
```c
```
---
```c++
```
---
```c#
```
---
```go
func lengthOfLongestSubstring(s string) int {
charLastPos := make(map[string]int)
ans, start := 0, 0
for i := range s {
si := string(s[i])
if lastPos, ok := charLastPos[si]; ok {
start = max(start, lastPos)
}
// 如果都没有重复字母,这里必须要 +1
ans = max(ans, i - start + 1)
// 为了对应上面 +1,这里也 +1
charLastPos[si] = i + 1
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
```
---
```java
```
---
```javascript
```
---
```kotlin
```
---
```php
```
---
```python
```
---
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
char_last_pos = {}
start, ans = 0, 0
for i in range(len(s)):
if s[i] in char_last_pos:
start = max(start, char_last_pos[s[i]])
# 如果都没有重复字母,这里必须要 +1
ans = max(ans, i - start + 1)
# 为了对应上面 +1,这里也 +1
char_last_pos[s[i]] = i + 1
return ans
```
---
```ruby
```
---
```rust
```
---
```scala
```
---
```swift
```
---
```typescript
```
---
叶王 © 2013-2024 版权所有。如果本文档对你有所帮助,可以请作者喝饮料。