No.003：Longest Substring Without Repeating Characters

題目：

Given a string, find the length of the longest substring without repeating characters.
Example:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.

官方難度：

Medium

翻譯：

給定一個字元串，找出最長子串，字串中無重覆字元。

例子：

abcabcbb最長字串為abc，長度為3

bbbbb最長字串為b，長度為1

pwwkew最長字串是wke，長度為3

註意，結果必須是字串，如pwke就不是例子3中的最長字串

思路：

1.用一個變數存儲最大值，從頭開始遍歷字元串，每次增加新元素，對舊元素做一次判斷，之後比較最大值。

解題中可能遇到的困難：

1.遇到重覆字元串的時候，需要重置比較字元串，而且不是清空，是長度為1的當前重覆字元串。

2.因為只有當遇到重覆字元串的時候，當前比較字元轉的append()工作會停止，然後再與最長字元串比較，所以最長字元串在末尾的情況要特殊考慮。

解題代碼：

 1 private static String method(String str) {
 2         int maxLength = 0;
 3         // 結果集
 4         StringBuffer result = new StringBuffer();
 5         StringBuffer temp = new StringBuffer();
 6         String tempStr;
 7         for (int i = 0; i < str.length(); i++) {
 8             tempStr = str.substring(i, i + 1);
 9             // 不存在重覆
10             if (!isExist(temp, tempStr)) {
11                 temp.append(tempStr);
12             } else {
13                 // 遇到重覆，比較最大長度
14                 if (temp.length() > maxLength) {
15                     // temp超過最大長度，保存結果
16                     maxLength = temp.length();
17                     result = temp;
18                 }
19                 // 無論超過與否，都要重置temp，temp的值是當前的判斷到重覆的字元串
20                 temp = new StringBuffer(tempStr);
21                 continue;
22             }
23             // 特殊情況考慮：最長字元串在原字元串尾部
24             if (i == str.length() - 1) {
25                 if (temp.length() > maxLength) {
26                     // 最後一個，沒必要給maxLength賦值了，雖然這個值錯了
27                     result = temp;
28                 }
29             }
30         }
31         return result.toString();
32     }
33 
34     // 判斷check字元，是否存在於sb欄位中
35     private static boolean isExist(StringBuffer sb, String check) {
36         for (int i = 0; i < sb.length(); i++) {
37             if (sb.substring(i, i + 1).equals(check)) {
38                 // true表示存在重覆
39                 return true;
40             }
41         }
42         return false;
43     }

測試代碼地址：

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q003.java

LeetCode題目地址：

https://leetcode.com/problems/longest-substring-without-repeating-characters/

PS：如有不正確或提高效率的方法，歡迎留言，謝謝！