Tuesday, April 22, 2014

Longest Substring Without Repeating Characters

public class Solution {// Note: this solution is not accepted, I will update it later.
       public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int maxLen = 0, i = 0;
        // for(int i = 0; i < s.length(); i ++){
       
        StringBuffer uniqSubSB = new StringBuffer();
        while(i < s.length()){
            // if(uniqSubSB.length() != 0) uniqSubSB.delete(0, uniqSubSB.length());
       
            if(checkRepeat(uniqSubSB,s.charAt(i)) < 0){
                uniqSubSB.append(s.charAt(i));
                i ++;
                if(i == s.length()){// In the case where this index has meet the end of string
                return Math.max(maxLen, uniqSubSB.length());
                }
            }
            else{  
                maxLen = Math.max(maxLen, uniqSubSB.length());
                uniqSubSB.delete(0, uniqSubSB.length());
                i = s.lastIndexOf(String.valueOf(s.charAt(i)),i - 1) + 1;// start next search from the last "same"                                                                                                          // char before (i -1)
            }
        }
        return maxLen;
    }
   
    public int checkRepeat(StringBuffer uniqSubSB, char c){// The O(n^2) time might be due to this method,
        if(uniqSubSB.length() == 0) return -1;
        //String current = String.valueOf(s.charAt(i));
        int idx = uniqSubSB.toString().indexOf(String.valueOf(c));
        return idx;
    }
}

UPDATE:

public class Solution {
       public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;
        int maxLen = 0, i = 0;
        // for(int i = 0; i < s.length(); i ++){
       
        StringBuffer uniqSubSB = new StringBuffer();
        boolean[] checkAppear = new boolean[256];// Only 256 chars, so this array can store a flag indicating                                                                             //whether the char has existed. Accelerate check speed.
        Arrays.fill(checkAppear,false);
        while(i < s.length()){
            if(!checkAppear[s.charAt(i)]){// check
                checkAppear[s.charAt(i)] = true;
                uniqSubSB.append(s.charAt(i));
                i ++;
                if(i == s.length()){
                return Math.max(maxLen, uniqSubSB.length());
                }
            }
            else{  
                Arrays.fill(checkAppear,false);
                maxLen = Math.max(maxLen, uniqSubSB.length());
                uniqSubSB = new StringBuffer();
                i = s.lastIndexOf(String.valueOf(s.charAt(i)),i - 1) + 1;
            }
        }
        return maxLen;
    }
}

No comments:

Post a Comment