3. 无重复字符的最长子串

无重复字符的最长子串 #

题目 #

给定一个字符串,请你找出其中不含有重复字符的   最长子串   的长度。 示例  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 ```
---

本文访问量

本站总访问量

本站总访客数