Leetcode --- Longest Substring without Repeating Characters(Medium)
===

## Description

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

### Example

* Ex1:
**Input**: s = "abcabcbb"
**Output**: 3
**Explanation**: The answer is "abc", with the length of 3.

* Ex2:
**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.

* Ex3:
**Input**: s = ""
**Output**: 0

### Constrains:

* 0 <= s.length <= 5 * 10^4^
* s consists of English letters, digits, symbols and spaces.

## Solution:
用hash檢查是否有重複,若遇到重複則統計一次長度,但**下一次的起始點需要在重複點的下一個** ,才不會少算長度.另外就是如何減少重複比較,寫法因為受限於hash的method,所以就直接clear後再重新put進hash.

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] chs = s.toCharArray();
        Map<Character,Integer> h1 = new HashMap<>();
        
        int count =0;
        int entry= 0;
        int i =0;
        while(i<chs.length)
        {
            if(h1.containsKey(chs[i]) == false)
            {
               h1.put(chs[i],i); 
                
                if(i == chs.length -1)
                {
                    int k = i-entry +1;
                    if(k>count)
                        count =k;
                }
            }
            else
            {
                int k = i - entry;
                if(k>count)
                    count = k;
                
               int newEntry = h1.get(chs[i]) +1 ;
                entry =newEntry ;
                
                h1.clear();
                while(newEntry <= i)
                {
                    h1.put(chs[foo],newEntry);
                    newEntry++;
                }
            }
            i++;
        }
        return count;
    }
}

**line 16~20:** 對最後一位元做處理,因為最後一個未重複(line 12進入)故k要+1(算自己)
**line 29:** 找到在hash中跟當前i重複的人,從他的下一個繼續數
**line 33:** 接著line 29,因為從他下一個到當前i,在之前的迴圈已判斷過皆無重複,故直接put進hash.

### Submissions on Leetcode

Runtime: **56 ms**, faster than **17.73%** of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: **39.4 MB**, less than **30.73%** of Java online submissions for Longest Substring Without Repeating Characters.

## Complexity Analysis

最差的情況發生在首尾字元重複且中間各不相同,會讓newEntry迴圈跑n-1次
=> ==O(n^2^)==

###### tags: `Leetcode` `Medium` `String`