Saturday, August 24, 2013

longest substring without any repetition of characters


I'm not using java very often. This program serves as a good practice for playing with String and Hashtable in java.


/* Write a code to find out longest substring without any repetition of characters with O(n) complexity. */
import java.util.*;

public class longestSubstring {
     public static String longestsubstr(String s) {
         Hashtable<Character, Integer> visited = new Hashtable<Character, Integer> ();
         String sub = new String();
         int start = 0;
         for (int i = 0; i < s.length(); ++i) {
              if (visited.containsKey(s.charAt(i))) {
                   if (i-start > sub.length()) {
                       sub = s.substring(start, i);                      
                   }
                   for (int j = start; j < visited.get(s.charAt(i)); ++j) {
                       visited.remove(s.charAt(j));
                   }
                   start = visited.get(s.charAt(i)) + 1;
                   visited.put(s.charAt(i), i);
              } else {
                   visited.put(new Character(s.charAt(i)), i);                                     
              }
         }
         if (s.length() - start > sub.length()) {
              sub = s.substring(start, s.length());
         }
         return sub;
     }
    
     public static void main(String args[]) {
         String str = "aaa1234abcde";
         System.out.println(longestsubstr(str));
         String str2 = "0123456756777890123456";
         System.out.println(longestsubstr(str2));        
     }

}

No comments:

Post a Comment