---
tags: LeetCode
---

# 3. Longest Substring Without Repeating Characters (Medium)
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.

輸入範本如下

public class Solution {
    public int LengthOfLongestSubstring(string s) {
    }
}

### 直覺想法
這題我覺得頗難 Orz. 沒想法
偷看一下解法後 , 發現可以用 Sliding Window 的概念去解.

1. 走訪字串過程中 , 若發現該字存在於 set 中 , 則移除 l 指標所指向的字 , 直到移除該字為止. 若不存在於 set 中 , 則計算此段的連續不重複字串的長度是否大於前者 , 若是則取代前者.

96 ms	25.7 MB
You are here!
Your runtime beats 51.60 % of csharp submissions.
public int LengthOfLongestSubstring(string s)
{
    HashSet<char> set = new HashSet<char>();
    int max = 0;
    for (int l = 0, r = 0; r < s.Length;)
    {
        if (!set.Contains(s[r]))
        {
            max = Math.Max(r - l + 1, max);
            set.Add(s[r++]);
        }
        else
        {
            set.Remove(s[l++]);
        }
    }
    return max;
}

2. 若是有紀錄位置 , 則 l 的移動可以一步到位 , 不需要一次一次移動.
- 使用 Dictinary 實作

    84 ms	25.9 MB
    You are here!
    Your runtime beats 82.65 % of csharp submissions.
    public int LengthOfLongestSubstring(string s)
    {
        Dictionary<char, int> dict = new Dictionary<char, int>();
        int max = 0;
        for (int l = 0, r = 0; r < s.Length; r++)
        {
            if (dict.ContainsKey(s[r]))
            {
                l = Math.Max(l, dict[s[r]]);
            }
            dict[s[r]] = r + 1;
            max = Math.Max(r - l + 1, max);
        }
        return max;
    }

- 使用 int[] 實作

    80 ms	25.9 MB
    You are here!
    Your runtime beats 91.75 % of csharp submissions.
    public int LengthOfLongestSubstring(string s)
    {
        int[] dict = new int[256];
        int max = 0;
        for (int l = 0, r = 0; r < s.Length; r++)
        {
            l = Math.Max(l, dict[s[r]]);
            max = Math.Max(max, r - l + 1);
            dict[s[r]] = r + 1;
        }
        return max;
    }

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: