This is a loop approach. The hard part is how to update the cur position when loop to a char same as between current position and loop position. (use while loop from cur position to the first char same as loop position) The other hard part is during the while loop to the first Char, need to update the char count array (256), chars between old cur to new cur (first dup as loop position + 1) to be count as 0, since a new count will begin, they are free if appear after loop, as they will count into next substring. All before cur current position, count will be 0.
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null){
return Integer.MIN_VALUE;
}
int maxLength = 0;
int curPos = 0;
int loopPos = 0;
boolean[] record = new boolean[256];
while(loopPos < s.length()){
if(record[s.charAt(loopPos)]){
if((loopPos - curPos) > maxLength){
maxLength = loopPos - curPos;
}
while(s.charAt(curPos) != s.charAt(loopPos)){
record[s.charAt(curPos)] = false;
curPos++;
}
loopPos++;
curPos++;
}else{
record[s.charAt(loopPos)] = true;
loopPos++;
}
}
if(s.length() - curPos > maxLength){
maxLength = s.length() - curPos;
}
return maxLength;
}
}
没有评论:
发表评论