2015年9月15日星期二

Leetcode 3 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.

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;  
   }  
 }  

没有评论:

发表评论