博客

输入一串字符串，输出最长的不重复子串

题目描述

给定一个字符串，返回最长无重复子串(无重复指的是所有字符都不相同)。

示例

输入 qqwerayy，返回 qweray

输入 qwerqwet，返回 rqwet

输入 qwqwqwqw，返回 qw

show the code as follow:

package math;

import org.junit.Test;

/**
 * 输入一个字符串，返回最长的不重复的子串
 * @author jsyuger
 * eg:输入qqwerayy，返回qweray
 *    输入qwerqwet，返回rqwet
 *    输入qwqwqwqw，返回qw
 *    说明：如有多个最长子串，返回第一个最长子串
 */
public class MaxSubstring {
	
	@Test
	public void test() {
		String []s = {"qqwerayy" , "qwerqwet" , "qwqwqwqw"};
		for(String str:s) {
			System.out.println(str+"最长不重复子串是："+MaxSubStr(str));
		}
	};
	
	/**
	 * 求最长的不重复的子串的实现方法
	 * @param str 母串
	 * @return
	 */
	public String MaxSubStr(String str) {
		char a[] = str.toCharArray(); //将字符串字符数组化
		int max = 1 ; //最大长度
		String maxSub = str.substring(0,1); //最长不重复子串
		int i = 0 , j=1 ; //定义两个指针，用于动态锁定不重复子串
		boolean flag = false; //是否出现相同的字符标志
		
		//外层循环，针对i的位置移动
		while(i<=a.length-2 && j<=a.length -1) {
			//内层循环，针对j的位置移动
			while(i<=a.length-2 && j<=a.length -1) {
				//j指针移动过程中，若出现了相同字符，flag设置为true，并跳出while循环
				for(int k=i;k<j;k++) {
					if(a[k] == a[j]) flag = true;
				}
				if(flag) break;
				j++; //若flag为false，j继续向前移动
			}
			
			//出现相同字符后，比较新子串长度j-i和原来最长子串长度max
			if(max<j-i) {
				max = j-i ;
				maxSub = str.substring(i, j);			
			}
			
			//i和j指针同时向前移动，并初始化flag为false
			i++;
			j=i+1;
			flag = false;
			
		}
		
		//返回最长子串
		return maxSub;
	}
	

}