Brooke

一、題目

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.

 

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

 

二、程式作法

/*
思路1：一開始就拿最大的字串，並確認該字串裡的所有字元沒有重複，
如果沒有找到，則拿「最大的字串」寬度-1的長度來比，如果沒有找到再以該寬度整個往前一位子，繼續比，
如果沒有找到，則拿「最大的字串」寬度-2的長度來比，依續之前方法，直到找出沒有重複的最大字串為止。
這個方法可求解，但最後還是拋出了Time Limit Exceeded

思路2：sliding window problem
參考https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/665796/c
*/
/*
演示範例1：輸入為 "pwwkew"
觀注字串內容的演進為
p
pw
 w
  
  w
  wk
  wke
   ke
   kew

演示範例2：輸入為 "abcabcdeabc"
a
ab
abc
 bc
 bca
  ca
  cab
   ab
   abc
   abcd
   abcde
    bcde
    bcdea
     cdea
     cdeab
      deab
      deabc
*/
public class Solution
{
    public int LengthOfLongestSubstring(string s)
    {
        int maxLength = 0;
        int left = 0;
        int right = 0;

        HashSet<char> set = new HashSet<char>();

        while (right < s.Length)
        {
            if (set.Contains(s[right]))
            {
                set.Remove(s[left]);
                left++;
            }
            else
            {
                set.Add(s[right]);
                maxLength = Math.Max(maxLength, set.Count);
                right++;
            }
        }

        return maxLength;
    }
}

 

三、思路筆記

目的為找出最大不重複字元的子字串之長度。

一開始宣告「左、右」兩指標，左右兩指標所框起來的範圍就是所要觀注的子字串，

配合 HashSet (Hash Table) 其可用來裝所要觀注的子字串，

觀注的子字串裡需沒有重複的字元，並且每次右指標在擴張時，

記錄其最大的字串長度。