# LeetCode Solution, Medium, 3. Longest Substring Without Repeating Characters

# [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

## 題目敘述

Given a string `s`, find the length of the **longest substring** without repeating characters.

**Example 1:**

    Input: s = "abcabcbb"
    Output: 3
    Explanation: The answer is "abc", with the length of 3.

**Example 2:**

    Input: s = "bbbbb"
    Output: 1
    Explanation: The answer is "b", with the length of 1.

**Example 3:**

    Input: s = "pwwkew"
    Output: 3
    Explanation: The answer is "wke", with the length of 3.
    Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

**Example 4:**

    Input: s = ""
    Output: 0

**Constraints:**

- `0 <= s.length <= 5 * 10**4`
- `s` consists of English letters, digits, symbols and spaces.

### 題目翻譯

給定一個字串 `s` ，然後要找出其中最長的子字串，其中這個子字串的字母都只能視唯一值，不能重複。

## 解法解析

這題的解法使用了 Sliding Window，一個個慢慢地滑動來找。這邊用一個 hash map 來儲存已經遍歷過的 char 的 index，當下次遇到相同的 char 就從當時的 index 重新計算長度。

### 解法範例

#### Go

```go
func lengthOfLongestSubstring(s string) int {
	var ans int
	var mp = make(map[rune]int)

	var i int
	for j, c := range s {
		if val := mp[c]; val > 0 {
			i = max(val, i)
		}
		ans = max(ans, j-i+1)
		mp[c] = j + 1
	}
	return ans
}

func max(x int, y int) int {
	if x > y {
		return x
	}
	return y
}
```

#### JavaScript

```javascript
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let ans = 0;
    const mp = {};
    for (let i = 0, j = 0; j < s.length; j++) {
        if (s[j] in mp) {
            i = Math.max(mp[s[j]], i);
        }
        ans = Math.max(ans, j - i + 1);
        mp[s[j]] = j + 1;
    }
    return ans;
};
```

#### Kotlin

```kotlin
class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        var ans = 0
        val mp = mutableMapOf<Char, Int>()

        var i = 0
        for ((j, char) in s.withIndex()) {
            if (mp.keys.contains(char)) {
                i = Math.max(i, mp[char]!! + 1)
            }

            ans = Math.max(ans, j - i + 1)
            mp[char] = j
        }
        return ans
    }
}
```

#### PHP

```php
class Solution
{

    /**
     * @param String $s
     * @return Integer
     */
    function lengthOfLongestSubstring($s)
    {
        $ans = 0;
        $mp = [];

        $i = 0;
        for ($j = 0; $j < strlen($s); $j++) {
            if (isset($mp[$s[$j]])) {
                $i = max($i, $mp[$s[$j]]);
            }
            $ans = max($ans, $j - $i + 1);
            $mp[$s[$j]] = $j + 1;
        }
        return $ans;
    }
}
```

#### Python

```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        # mp stores the current index of a character
        mp = {}

        i = 0
        # try to extend the range [i, j]
        for j, char in enumerate(s):
            if char in mp:
                i = max(mp[char], i)

            ans = max(ans, j - i + 1)
            mp[char] = j + 1

        return ans
```

#### Rust

```rust
use std::cmp::max;
use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut m = HashMap::new();
        let mut ans = 0;
        let mut i = -1;
        let mut current = 0;
        for c in s.chars() {
            if let Some(last) = m.insert(c, current) {
                i = max(i, last);
            }
            ans = max(ans, current - i);
            current += 1;
        }
        ans
    }
}
```

#### Swift

```swift
class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var ans = 0
        var mp: [Character: Int] = [:]

        var i = 0
        for (j, char) in s.enumerated() {
            if let val = mp[char] {
                i = max(i, val)
            }

            ans = max(ans, j - i + 1)
            mp[char] = j + 1
        }
        return ans
    }
}
```