求字符串的最长不重复子串

题目要求：找到一个字符串中的一个连续子串，这个子串内不能有任何两个字符是相同的，
并且这个子串是符合要求的最长的。
例如：abcdeab，这个字符串有很多不重复子串，比如：abcde, bcdea, cdeab都是不重复子串，
而且都是最长的。
//试验例子 abceaefk  abceaaaaaa

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class LongestsubString {

	public static void main(String[] args) {
		print(getLongestNoRepeatSubString("abceafb"));

	}
	private static void print(List list) {
		for(Iterator it=list.iterator();it.hasNext();){
			System.out.println(it.next());
		}
		
	}
	public static List getLongestNoRepeatSubString(String src){
		char[] arr=src.toCharArray();
		int len=arr.length;//数组长
		List<String> subList=new ArrayList<String>();//最长的子串可能会有多少，用这个临时保存
		int max;//最长子段长度
		int start;//最长子段的开始位置
		Map<Character,Integer> charMap=new HashMap();//保存对应字符及其最后出现的位置		
		max=start=0;
		int i;
		for(i=0;i<len;i++){
			if(!charMap.containsKey(arr[i])){//不包含的话就加入到map中
				charMap.put(arr[i], i);				
			}else{//包含的话就得处理了,看在重复出现前的子串是否是更长
				int pre=charMap.get(arr[i]);			
				int tempLen=i-start;//当前子串长度							
				if(tempLen>=max){//找到新的最长子串了
					if(tempLen>max)subList.clear();//需要刷新列表
					max=tempLen;
					subList.add(src.substring(start, i));//保存这个最长子串					
					charMap.put(arr[i], i);//置成新的位置					
				}else{									
					charMap.put(arr[i], i);//置成新的位置
				}
				start=pre+1;//只要重复了，都得重新开始设置start的位置
			}
		}	
		if(i-start>=max){//这个主要是处理这种情况：abcd 没有重复的~~
			if(i-start>max)subList.clear();
			subList.add(src.substring(start, i));
		}
		return subList;
	}
}

 

评论

1 楼 MCQCM 2016-04-22  

你的代码有个小问题，不信，你试试abceaefkbn。正确如下：


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
public class LongestsubString {

public static void main(String[] args) {
print(getLongestNoRepeatSubString("abceabfkbn"));

}
private static void print(List list) {
for(Iterator it=list.iterator();it.hasNext();){
System.out.println(it.next());
}

}
public static List getLongestNoRepeatSubString(String src){
char[] arr=src.toCharArray();
int len=arr.length;//数组长
List<String> subList=new ArrayList<String>();//最长的子串可能会有多少，用这个临时保存
int max;//最长子段长度
int start;//最长子段的开始位置
Map<Character,Integer> charMap=new HashMap();//保存对应字符及其最后出现的位置
max=start=0;
int i;
for(i=0;i<len;i++){
if(!charMap.containsKey(arr[i])){//不包含的话就加入到map中
charMap.put(arr[i], i);
}else{//包含的话就得处理了,看在重复出现前的子串是否是更长
int pre=charMap.get(arr[i]);
if(pre<start)
continue;
int tempLen=i-start;//当前子串长度
if(tempLen>=max){//找到新的最长子串了
if(tempLen>max)subList.clear();//需要刷新列表
max=tempLen;
subList.add(src.substring(start, i));//保存这个最长子串
charMap.put(arr[i], i);//置成新的位置
}else{
charMap.put(arr[i], i);//置成新的位置
}
start=pre+1;//只要重复了，都得重新开始设置start的位置
}
}
if(i-start>=max){//这个主要是处理这种情况：abcd 没有重复的~~
if(i-start>max)subList.clear();
subList.add(src.substring(start, i));
}
return subList;
}
}