3. 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.

解法解析

解法範例

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

``````/**
* @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

``````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

``````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

``````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

``````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

``````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
}
}
``````