个人记录-LeetCode 3.Longest Substring Without Repeating Characters

问题： Given a string, find the length of the longest substring without repeating characters.

Examples:

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.

代码示例： 1、失败的O($N^2$)算法，可行但运行超时

public class Solution { public int lengthOfLongestSubstring(String s) { int max = 0; if (s != null) { int length = s.length(); //i表示不重复字符串的起始位置 //当i位置后的字符串数量小于当前的max时，就没有继续搜索的必要了 for (int i = 0; i < length - max; ++i) { int curMax = searchFromCurIndex(i, s, length); max = curMax > max ? curMax : max; } } return max; } int searchFromCurIndex(int index, String str, int length) { int next; //next用来表示新加入的字符 for (next = index + 1; next < length; ++next) { //新加的字符与已有的不重复，则继续增加下一个 if (str.substring(index, next).contains(String.valueOf(str.charAt(next)))) { break; } } return next - index; } }

这里存在的问题是：当检测到重复的字符时，下一次搜索应该越过重复的位置。 举例来说： abcdef是个不重复的子串，abcdefc中前后两个c重复了。 那么下一次搜寻，应该跨过出现重复的地方进行，否则找出来的候选串依然有重复字符，且长度还不如上次的搜索。 所以下一次搜索，直接从第一个c的下一个字符d开始进行。

从宏观来讲，O(N2)算法的失败之处是：没有充分利用前一次搜索获得的有效信息。

2、改进的O(N)算法

class Solution { public int lengthOfLongestSubstring(String s) { if (s == null || s.length() == 0) { return 0; } int len = 0; int start = 0; int end = start; String subStr; for (int i = 0; i < s.length(); ++i) { subStr = s.substring(start, end); char curr = s.charAt(i); int index = subStr.indexOf(curr); if (index != -1) { int newLen = end - start; if (newLen > len) { len = newLen; } start = start + index + 1; } ++end; } int newLen = end - start; if (newLen > len) { len = newLen; } return len; } }