首页 > 代码库 > Longest Substring Without Repeating Characters
Longest Substring Without Repeating Characters
https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
解题思路：
这种题目用暴力遍历显然不可。因为往后遍历的最长长度，取决于前面的情况，考虑用动态规划的方法求解。动态规划问题的关键是建立每个状态的模型，建立一个数学中的递推公式。
与maxlength subarray的问题类似，这里考虑以i - 1位置结尾的没有重复字符的最长字符为S[i-1]，长度为f(i - 1)，i处的字符为C[i]，我们来讨论f(i)的大小。
如果S[i - 1]里没有i处的字符，显然f(i) = f(i - 1) + 1。如果S[i - 1]里有i处的字符，那么必然只有一个，所以f(i) = 从S[i-1]内i字符后面开始算起，算到i为止。代码如下。仅仅遍历一遍，在O(n)的时间内就可以解决问题了。
public class Solution { public int lengthOfLongestSubstring(String s) { int maxLength = 0; int start = 0; for(int i = 0; i < s.length(); i++){ // length = i - start; if(s.substring(start, i).indexOf(s.charAt(i)) == -1){ maxLength = Math.max(maxLength, i - start + 1); //}else if(s.substring(start, i).indexOf(s.charAt(i)) == 0){ //maxLength不变 // start++; }else { start = start + s.substring(start, i).indexOf(s.charAt(i)) + 1; //start = i; } } return maxLength; }}
事实上，S[i - 1]内有i处字符的情况也可以计算长度。代码如下。
public class Solution { public int lengthOfLongestSubstring(String s) { int maxLength = 0; int start = 0; for(int i = 0; i < s.length(); i++){ // length = i - start; if(s.substring(start, i).indexOf(s.charAt(i)) == -1){ //start不变 maxLength = Math.max(maxLength, i - start + 1); //}else if(s.substring(start, i).indexOf(s.charAt(i)) == 0){ //maxLength不变 // start++; }else { start = start + s.substring(start, i).indexOf(s.charAt(i)) + 1; maxLength = Math.max(maxLength, i - start + 1); //start = i; } } return maxLength; }}
事实上，上述两个if分支可以合并，start的坐标计算不管i有没有在S[i - 1]内出现，都能得到计算。于是，代码进一步精简如下。
public class Solution { public int lengthOfLongestSubstring(String s) { int maxLength = 0; int start = 0; for(int i = 0; i < s.length(); i++){ start = start + s.substring(start, i).indexOf(s.charAt(i)) + 1; maxLength = Math.max(maxLength, i - start + 1); } return maxLength; }}
至此，该dp算法可以表述为，dp[i]等于S[i - 1]里面，从与C[i]相同的后一个字符算起，到C[i]的长度。C[i]为i处的字符。如果S[i - 1]内没有C[i]，显然应该+1的。事实上indexOf(C[i]) = -1，所以后一个字符就是从0开始算，即+1。最后再计算所有dp[i]的最大值，即为maxLength。
还要注意的是，这里不可取不同情况下的max。即，不能出现一个在S[i - 1]内已经有的C[i]，就将整个S[i - 1]丢弃，从C[i]开始，不可！
这里还可以用一个HashMap记录所有字符出现的位置，然后再用map.contains判断是不是有这个字符，其实和indexof是一样的。
Longest Substring Without Repeating Characters