LeetCode #3 Longest Substring Without Repeating Characters

By JJ.Chang 2024-01-11 Leet code

1. 題目（Problem Statement）

  • 英文：

    Given a string s, find the length of the longest substring without repeating characters.

  • 中文：

    給定一個字符串 s，找到最長的不重複字符的子字符串的長度。

2. 題目說明與解決方案（Explanation and Solution）

我們需要找出一個字符串中不含重複字符的最長子串的長度，不重複區間的定義，就是區間內的每個字元都不相同。

例如，對於字符串 “abcabcbb”，最長的不含重複字符的子串是 “abc”，其長度為 3。

我們可以使用滑動窗口的方法。使用兩個指標，一個指向子串的開始，另一個不斷向右移動，每次擴展一個字符。使用哈希集合來記錄當前子串中的字符，當發現重複字符時，移動左指標，直到消除重複為止。

3. 範例（Example）

 1Example 1:
 2	Input: s = "abcabcbb"
 3	Output: 3
 4	Explanation: The answer is "abc", with the length of 3.
 5---
 6Example 2:
 7	Input: s = "bbbbb"
 8	Output: 1
 9	Explanation: The answer is "b", with the length of 1.
10---
11Example 3:
12	Input: s = "pwwkew"
13	Output: 3
14	Explanation: The answer is "wke", with the length of 3.
15	Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 3 最長的不重複子串是 “wke”，長度為 3。答案必須是子串，而 “pwke” 是一個子序列而不是子串。

4. 限制條件（Constraints）

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、數字、符號和空格組成

5. C# 解法（C# Solution）

 1namespace UnitTestDay3_LongestSubstring
 2{
 3    public class Solution
 4    {
 5        public int LengthOfLongestSubstring( string s )
 6        {
 7            int n = s.Length;
 8            HashSet<char> set = new HashSet<char>();
 9            int maxLength = 0, left = 0, right = 0;
10
11            while (right < n)
12            {
13                if (!set.Contains( s[right] ))
14                {
15                    set.Add( s[right] );
16                    maxLength = Math.Max( maxLength, right - left + 1 );
17                    right++;
18                }
19                else
20                {
21                    set.Remove( s[left] );
22                    left++;
23                }
24            }
25
26            return maxLength;
27        }
28    }
29}

6. C# 程式碼說明（C# Code Explanation）

  • 我們使用滑動窗口的方法，兩個指標 left 和 right 分別表示子串的開始和結束。
  • HashSet 用於儲存當前子串中的字符，以判斷是否有重複。
  • 當發現重複字符時，移動左指標 left，直到消除重複。
  • 每次向右擴展子串，更新最長子串的長度。

leetCode03

以下是程式碼的詳細解釋：

  1. 初始化變數：

    • n：字串**s**的長度。
    • set：用來存儲目前子字串中獨一無二字元的HashSet。
    • maxLength：不含有重複字元的子字串的最大長度。
    • left 和 right：定義目前子字串的兩個指標。

  2. 透過滑動窗口的方式遍歷字串：

    • 如果 right 指標所指的字元不在HashSet中：

      1. 把該字元加入HashSet。
      2. 如果目前子字串的長度大於之前的最大長度，則更新 maxLength。
      3. 把 right 指標移到下一個位置。

    • 如果 right 指標所指的字元已經在HashSet中：

      1. 把 left 指標所指的字元從HashSet中移除。
      2. 把 left 指標移到下一個位置。

  3. 重複上述過程，直到 right 指標到達字串的結尾。

  4. 返回找到的最大長度。

7. C# 單元測試（C# Unit Tests）

 1namespace UnitTestDay3_LongestSubstring.Tests
 2{
 3    [TestClass()]
 4    public class SolutionTests
 5    {
 6        private Solution UT = new Solution();
 7
 8        [TestMethod]
 9        public void Test1()
10        {
11            int result = UT.LengthOfLongestSubstring( "abcabcbb" );
12            Assert.AreEqual( 3, result );
13        }
14
15        [TestMethod]
16        public void Test2()
17        {
18            int result = UT.LengthOfLongestSubstring( "bbbbb" );
19            Assert.AreEqual( 1, result );
20        }
21
22        [TestMethod]
23        public void Test3()
24        {
25            int result = UT.LengthOfLongestSubstring( "pwwkew" );
26            Assert.AreEqual( 3, result );
27        }
28    }
29}

8. Python 解法（Python Solution）

 1class Solution:
 2    def length_of_longest_substring(self, s: str) -> int:
 3        n = len(s)
 4        max_length = 0
 5        left, right = 0, 0
 6        char_set = set()
 7
 8        while right < n:
 9            if s[right] not in char_set:
10                char_set.add(s[right])
11                max_length = max(max_length, right - left + 1)
12                right += 1
13            else:
14                char_set.remove(s[left])
15                left += 1
16
17        return max_length

9. Python 程式碼說明（Python Code Explanation）

  • 使用滑動窗口的概念，兩個指針 left 和 right 指示子字串的範圍。
  • 使用 set 來儲存子字串中的字元，以檢查重複。
  • 在遍歷過程中，不斷更新最長子字串的長度。

10. Python 單元測試（Python Unit Tests）

 1import unittest
 2
 3class SolutionTests(unittest.TestCase):
 4    def test_length_of_longest_substring_case1(self):
 5        solution = Solution()
 6
 7        s = "abcabcbb"
 8        expected = 3
 9        result = solution.length_of_longest_substring(s)
10        self.assertEqual(expected, result)
11
12    def test_length_of_longest_substring_case2(self):
13        solution = Solution()
14
15        s = "bbbbb"
16        expected = 1
17        result = solution.length_of_longest_substring(s)
18        self.assertEqual(expected, result)
19
20    def test_length_of_longest_substring_case3(self):
21        solution = Solution()
22
23        s = "pwwkew"
24        expected = 3
25        result = solution.length_of_longest_substring(s)
26        self.assertEqual(expected, result)

11. 總結（Summary）

這個題目要求找出一個字串中不包含重複字元的最長子字串的長度。解決方案使用了滑動窗口的概念，使用兩個指針來表示子字串的範圍，並使用 HashSet 或 set 來檢查重複。

這個演算法的時間複雜度是O(n)，其中 n 是字串 s 的長度，因為每個字元最多被處理兩次（一次由 right 指標，一次由 left 指標）。空間複雜度為O(min(n, m))，其中m是字元的種類數目（獨一無二的數量）。在最壞的情況下，當所有字元都是唯一的時候，空間複雜度是O(n)。

Reference：Longest Substring Without Repeating Characters — Leetcode #3

comments powered by Disqus
>