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