題目敘述
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**4s consists of English letters, digits, symbols and spaces.
題目翻譯
給定一個字串 s ，然後要找出其中最長的子字串，其中這個子字串的字母都只能視唯一值，不能重複。
解法解析
這題的解法使用了 Sliding Window，一個個慢慢地滑動來找。這邊用一個 hash map 來儲存已經遍歷過的 char 的 index，當下次遇到相同的 char 就從當時的 index 重新計算長度。
解法範例
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
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
{
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 = {}
i = 0
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
}
}