title: Longest Substring Without Repeating Characters
body: <p>I have been spending hours on <a href="https://leetcode.com/problems/longest-substring-without-repeating-characters/" rel="nofollow noreferrer">Longest Substring Without Repeating Characters - LeetCode</a></p>
  
  <blockquote>
    <ol start="3">
    <li>Longest Substring Without Repeating Characters</li>
    </ol>
    
    <p>Medium</p>
    
    <p>Given a string, find the length of the <strong>longest substring</strong> without repeating characters.</p>
    
    <p><strong>Example 1:</strong></p>
  
  <pre><code>Input: "abcabcbb"
  Output: 3 
  Explanation: The answer is "abc", with the length of 3. 
  </code></pre>
    
    <p><strong>Example 2:</strong></p>
  
  <pre><code>Input: "bbbbb"
  Output: 1
  Explanation: The answer is "b", with the length of 1.
  </code></pre>
    
    <p><strong>Example 3:</strong></p>
  
  <pre><code>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.
  </code></pre>
  </blockquote>
  
  <p>The problem could be solved using two pointer mixed kadane's algorithms to manipulate subarray</p>
  
  <pre class="lang-py prettyprint-override"><code>class Solution:
      def lengthOfLongestSubstring(self, s: str) -&gt; int:
          logging.debug(f"{list(enumerate(s))}")
          slo = fas = 0  #slow as the fisrt character in a subarray which not duplicate, fast as the fast.
                                    #relation: length = fas - slo
          current = set()
          glo = loc = 0
          while fas &lt; len(s):
              logging.debug(f"pre_current: {current}, slow: {slo}, fast: {fas}")
              if s[fas] not in current: 
                  current.add(s[fas]
                  loc = fas - slo
                  glo = max(glo, loc)
                   fas +=1
              else:
                  current.remove(s[slo])
                  slo += 1
              logging.debug(f"post_current: {current}, slow: {slo}, fast: {fas} \n")
          return glo
  </code></pre>
  
  <p>TestCase </p>
  
  <pre class="lang-py prettyprint-override"><code>    def test_g(self):
          s = "abccefg"
          answer = 4
          check = self.solution.lengthOfLongestSubstring(s)
          self.assertEqual(answer, check)
  </code></pre>
  
  <p>The solution is very clear to move slow and fast alternatively</p>
  
  <pre class="lang-py prettyprint-override"><code>$ python 3.LongestSubstring.py MyCase.test_g
  DEBUG [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'c'), (4, 'e'), (5, 'f'), (6, 'g')]
  DEBUG pre_current: set(), slow: 0, fast: 0
  DEBUG post_current: {'a'}, slow: 0, fast: 1 
  
  DEBUG pre_current: {'a'}, slow: 0, fast: 1
  DEBUG post_current: {'b', 'a'}, slow: 0, fast: 2 
  
  DEBUG pre_current: {'b', 'a'}, slow: 0, fast: 2
  DEBUG post_current: {'b', 'c', 'a'}, slow: 0, fast: 3 
  
  DEBUG pre_current: {'b', 'c', 'a'}, slow: 0, fast: 3
  DEBUG post_current: {'b', 'c'}, slow: 1, fast: 3 
  
  DEBUG pre_current: {'b', 'c'}, slow: 1, fast: 3
  DEBUG post_current: {'c'}, slow: 2, fast: 3 
  
  DEBUG pre_current: {'c'}, slow: 2, fast: 3
  DEBUG post_current: set(), slow: 3, fast: 3 
  
  DEBUG pre_current: set(), slow: 3, fast: 3
  DEBUG post_current: {'c'}, slow: 3, fast: 4 
  
  DEBUG pre_current: {'c'}, slow: 3, fast: 4
  DEBUG post_current: {'c', 'e'}, slow: 3, fast: 5 
  
  DEBUG pre_current: {'c', 'e'}, slow: 3, fast: 5
  DEBUG post_current: {'e', 'f', 'c'}, slow: 3, fast: 6 
  
  DEBUG pre_current: {'e', 'f', 'c'}, slow: 3, fast: 6
  DEBUG post_current: {'g', 'e', 'f', 'c'}, slow: 3, fast: 7 
  
  .
  ----------------------------------------------------------------------
  Ran 1 test in 0.001s
  </code></pre>
  
  <p>As a conclusion, the solution employed two pointer technique and the idea of the Kadane algorithms. I assumed that it is possible to finally work it out after spending hours on debugging as a beginner.</p>
  
  <p>However, I read such a delicate solution </p>
  
  <pre class="lang-py prettyprint-override"><code>
  class SolutionA:
      def lengthOfLongestSubstring(self, s):
          """
          :type s: str
          :rtype: int
          """
          #slow is the first  which not duplicate in a subarray
          #fast is the last whichi not duplicate in a subarray
          lookup, glo, slo, fas = {}, 0, 0, 0
          for fas, ch in enumerate(s):
              if ch in lookup: 
                  slo = max(slo, lookup[ch]+1)
              elif ch not in lookup:
                  glo = max(glo, fas-slo+1)                
              lookup[ch] = fas #update the duplicates and add new 
          return glo
  </code></pre>
  
  <p>The solution is very smart, I honestly don't believe  one could design such a solution in hours if one did not read it before.</p>
  
  <p>It used hash map , two times of kadane's algorithms idea and very concise structure.</p>
  
  <p>Is it a common technique as two pointers? what's the name of it </p>