Longest Substring Without Repeating Characters (Java)

Leetcode

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.

	"1/26/2014 code rewrite"
	public class LongestSuStringWithoutRepeatCharacter {
	public int lengthOfLongestSubstring(String s) {
	if (s==null ||s.length()==0){
	return 0;
	}
	// record which char has been visited
	boolean [] checker=new boolean[256];
	// two pointers used to maintain longest distance without repeat
	int st=0;
	int ed=0;
	// max length
	int max=0;
	while(ed<s.length()){
	char c=s.charAt(ed);
	// no repeat, up date checker and max length
	if (!checker[c]){
	checker[c]=true;
	max=Math.max(ed-st+1,max);
	}
	else{
	// repeat happened, update checker, and make st pointer point to first unrepeat position
	while (s.charAt(st)!=c){
	checker[s.charAt(st)]=false;
	st++;
	}
	// skip the char cause repeat
	st++;
	}
	ed++;
	}
	return max;
	}
	}
	"For Brute Force Solution:"
	"To solve this question we can just use for loop to iterative substring from every "
	"position of this string and use a hashtable to help checking is there is a repeat"
	"character from current start position, if it is then break current loop and move "
	"forward 1 position for the begin position of substring, if not just put current"
	"character into hashtable.then current length of substring is the length of hashtable"
	"time complexity: O(n^2)"
	"space complexity: O(n);"
	import java.util.Hashtable;
	public class Solution {
	public int lengthOfLongestSubstring(String s) {
	if (s==null||s.length()==0) return 0;
	int maxlen=1;
	Hashtable<Character, Boolean> ht=new Hashtable<Character, Boolean>();
	for (int i=0; i<s.length(); i++){
	for (int j=i;j<s.length(); j++){
	if (ht.containsKey(s.charAt(j))){
	ht.clear();
	break;
	}
	else{
	ht.put(s.charAt(j),true);
	}
	int len=ht.size();
	if (len>maxlen){
	maxlen=len;
	}
	}
	}
	return maxlen;
	}
	}
	"More efficient Solution:"
	"assume the character composite the string is only ASCII, then we can build a Boolean[256] "
	"exist array for record if the character has appeared. if a character appeared, then from start point to"
	"the position(not include this position) may be maxlen , then we do once compare , then don’t forget mark"
	"all of the character before this repeat character in exist array as false. then both begin and end index "
	"increase 1. if current character not appeared, then we mark is as appeared in exist array, then end index"
	"increase 1. "
	"time complexity: O(n) (hint: Worst case: 2n because both begin and end index iterate once entire string)"
	"Space Complexity: O(n)"
	public class Solution {
	public int lengthOfLongestSubstring(String s) {
	Boolean [] exist =new Boolean [256];
	for (int i=0; i<256;i++){
	exist[i]=false;
	}
	int i=0;
	int j=0;
	int n=s.length();
	int maxlen=0;
	while(j<n){
	if (exist[s.charAt(j)]){
	maxlen=Math.max(maxlen,j-i);
	while(s.charAt(i)!=s.charAt(j)){
	exist[s.charAt(i)]=false;
	i++;
	}
	i++;
	j++;
	}
	else{
	exist[s.charAt(j)]=true;
	j++;
	}
	}
	return maxlen=Math.max(maxlen, n-i);
	}
	}

view raw LongestSuStringWithoutRepeatCharacter.java hosted with ❤ by GitHub