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.

題目翻譯

給定一個字串 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

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