Solution 1: Two pointer algorithm using slid window. Use flag array to store the count of each character in the window. Keep moving j, if see counter is 2 means 1st repeat. We need to update the result and then move i until see the same character, change the counter back to 1, move i to next. Then we start over again to move j. One thing to remember is: when go out of loop, need to update final result of Math.max(res,n-i).
public class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length();
int[] flag=new int[256];
int i=0, res=0;
for (int j=0; j<n; j++) {
if (++flag[s.charAt(j)]==2) {
res=Math.max(res,j-i);
while (--flag[s.charAt(i)]==0) i++;
i++;
}
}
res=Math.max(res,n-i);
return res;
}
}
没有评论:
发表评论