优化-从输入的字符串中截取最长的没有重复字符的子串

一次循环就可以了。当出现了一个前面已经出现的字符时，只需要将前面开始计数的位往后移n位(n取决于与前面的具体那一位字符重复)，并且计数减n，后面接着继续，并不需要从开始位重新循环。

import java.util.Set;
import java.util.TreeSet;
public class SubStr {
public static void main(String[] args) {
String input="abdabbsabcdefgssdwesskkkjl";
Set set = new TreeSet<String>();
for (int i = 0; i < input.length(); i++) {
set.add(input.charAt(i));
}
System.out.println(setToString(set,""));
}
public static String setToString(Set<?> set, String separator) {
if (set == null || set.isEmpty()) {
return "";
}
StringBuffer sb = new StringBuffer();
for (Object o : set) {
sb.append(o == null ? "null" : o.toString()).append(separator);
}
return sb.toString(); }
}

public class SubStr {
public static void main(String[] args) {
String input="abdabbsabcdefgssdwesskkkjl";
input = new StringBuffer(new StringBuffer(input).reverse().toString().replaceAll(
"(.)(?=.*\\1)", "")).reverse().toString();
System.out.println(input);
}
}

可以参考【连续子数组的最大和】
URL：http://www.cnblogs.com/Bob-FD/archive/2013/04/09/3010434.html这个

开始题没看全,你先看下这个，完善下。import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;public class ShortString { public static void main(String[] args) {
String str = "abdabbsabcdefgssdwesskkkjl";
change(str);
} public static void change(String str) {
List list = new ArrayList();
int beginIndex = 0;
int endIndex = str.length();
int index = 0;
for (int i = 0; i < endIndex-1; i++) {
if ((int) str.charAt(i) < (int) str.charAt(i + 1)
) {
index++;
if (i == endIndex - 2) {
list.add(str.substring(beginIndex, endIndex));
}
} else {
list.add(str.substring(beginIndex, index + 1));
beginIndex = index + 1;
index = index + 1;
}
}
System.out.println(list);
}
}

完整代码import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;public class ShortString { public static void main(String[] args) {
String str = "abdabbsabcdefgssdwesskkkjl";
change(str);
} public static void change(String str) {
List<String> list = new ArrayList<String>();
int beginIndex = 0;
int endIndex = str.length();
int index = 0;
for (int i = 0; i < endIndex-1; i++) {
if ((int) str.charAt(i) < (int) str.charAt(i + 1)
) {
index++;
if (i == endIndex - 2) {
list.add(str.substring(beginIndex, endIndex));
}
} else {
list.add(str.substring(beginIndex, index + 1));
beginIndex = index + 1;
index = index + 1;
}
}
String result = "";
int max = 0;
for(String string : list)
{
    max = Math.max(max,string.length());
    if(max == string.length())
     result = string;
}
System.out.println(result);
}
}

import java.util.*;public class SubStr {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
         String str = cin.nextLine();
         launch(str);
        }
    }

    public static void launch(String str) {
     StringBuilder sb = new StringBuilder();
     int length = 0;
     int maxLength = 0;
     String output = "";
     int start = 0;
     for(int i=0; i<str.length(); i++) {
     if(sb.indexOf((""+str.charAt(i)))==-1) {
     sb.append(str.charAt(i));
     length ++;
     } else {
     if(length > maxLength) {
     output = sb.toString();
     maxLength = length;
     }
     start = sb.indexOf(""+str.charAt(i))+1;
     sb = sb.delete(0, start);
     sb.append(str.charAt(i));
         length = length-start+1;
     }

     }
     if(length > maxLength) {
     output = sb.toString();
maxLength = length;
     }
     System.out.println(output);

    }
}

你截取的子串中是不是头尾不相同，，但是中间会没有重复的吗？
我试了试，好像不太会。你可以上代码吗？这个思路好像有点问题：1. 比如一个length=10的字符串，第9位和第10位重复，那把计数移到第9位，取到一个只有一个长的字符串显然是不对的；2. 判断一个字符在前面是否出现过，这个过程不是也要循环的吗？
我也没有想到解决办法，继续想，继续关注！

        public static void Main(String[] args)
        {
            Random ran = new Random();
            string str = string.Empty;
            for (int i = 0; i < 20; i++)
            {
                str += Convert.ToChar(ran.Next(1, 4).ToString());
            }
            Console.WriteLine(str);
            int k = 0;
            string result = string.Empty;
            string tempResult = string.Empty;
            while (k < str.Length - 1)
            {
                int n = k + 1;
                if (str[n] == str[k])
                {
                    tempResult += str[k];
                    if (result.Length < tempResult.Length)
                    {
                        result = tempResult;
                    }
                    tempResult = string.Empty;
                }
                else if (n != str.Length - 1)
                {
                    tempResult += str[k];
                }
                else
                {
                    tempResult += str[k];
                    tempResult += str[n];
                    if (result.Length < tempResult.Length)
                    {
                        result = tempResult;
                        tempResult = string.Empty;
                    }
                }

                k++;
            }
            Console.WriteLine(result);
            Console.Read();        }

总结一下，顺便也发个自己的public class GetMaxDistinctSubString {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
System.out.println("input string: ");
String str=scan.nextLine();
str=new GetMaxDistinctSubString().getDistinctSubstring(str);
System.out.println("substring :"+str);
}

String getDistinctSubstring(String original_str){
//方法一利用set的无重复性错误该方法只能获取一组不重复的值不能获取最大的不重复子串
/*Set<Character> set=new TreeSet<Character>();
for(int i=0;i<original_str.length();i++){
set.add(original_str.charAt(i));
}
return set.toString();*/
//方法二利用String.indexof(int ch,int fromIndex)
int maxLength=0;
int index=0;
for(int i=0;i<original_str.length();i++){
index=original_str.indexOf(original_str.charAt(i),i+1);
if(index!=-1){
return original_str.substring(0, index);
}
}
return original_str;

}

}

有bug 最新结果public class GetMaxDistinctSubString {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
System.out.println("input string: ");
String str=scan.nextLine();
str=new GetMaxDistinctSubString().getDistinctSubstring(str);
System.out.println("substring :"+str);
}

String getDistinctSubstring(String original_str){
//方法一利用set的无重复性错误该方法只能获取一组不重复的值不能获取最大的不重复子串
/*Set<Character> set=new TreeSet<Character>();
for(int i=0;i<original_str.length();i++){
set.add(original_str.charAt(i));
}
return set.toString();*/
//方法二利用String.indexof(int ch,int fromIndex)
int maxLength=original_str.length()-1;//取整个字符串
int index=0;
for(int i=0;i<original_str.length()&&i<maxLength;i++){//当遍历字符索引等于重复字符的最小位置即不重复字符串最大长度时终止
index=original_str.indexOf(original_str.charAt(i),i+1);
if(index!=-1&&maxLength>=index){
maxLength=index;
}
}
return original_str.substring(0,maxLength);

}

}

sorry 。我刚才的回复是没仔细看。你的程序好像还不是完全对的。假设输入的是："abdabbsabcdefgssdwesskkkjl" 这个字符串第一个没有重复的最长子串应该是
sabcdefg
长度为8你的结果:
abcdefgs
长度8

用你的代码运行了一遍运行结果不对后来看了你的代码发现你是用字母的int数来比的

public class ShortString {

    public static void main(String[] args) {
// String str = "abdabbsabcdefgssdwesskkkjl"; // 楼主给的字符串
// String str = "abcdefghijklmnopqrst"; // 最长子字符串为自己本身
// String str = "abcabcd";
        String str = "wabcdwjkhiw"; // 有两段相同长度的子字符串
    System.out.println(getDistinctSubString(str));
    }

    public static String getDistinctSubString(String input){
     if(!isHasSameChar(input)) return input;
     int maxDiff = 0; // 两个相同 char 的初始距离记录最长不重复子串的长度
     String result = ""; // 记录结果字符串
     for(int i = 0;i<input.length();i++){
     int diff = input.indexOf(input.charAt(i),i+1)-i;
     if(diff > 0 && diff==maxDiff){ // 如果前后有两端子字符串满足条件，那么都应该记录下来
     result += " - " +input.substring(i, i+diff) + " - " + moveFirstCharToLast(input.substring(i, i+diff));
     }
     if(diff > 0 && diff>maxDiff && !isHasSameChar(input.substring(i, i+diff))){
result = input.substring(i, i+diff) + " - " + moveFirstCharToLast(input.substring(i, i+diff));
maxDiff = diff;
     }
     if(diff <0 && !isHasSameChar(input.substring(i)) && (input.substring(i).length()> maxDiff )){
     return input.substring(i);
     }
     }
     return result;
    }

    public static boolean isHasSameChar(String str){ // 判断一个String是否含有相同 char
     for(int i=0;i<str.length();i++){
     if((str.indexOf(str.charAt(i),i+1))>0)return true;
     }
     return false;
    }

    public static String moveFirstCharToLast(String str){ // 转移首字符到最后
     if(str.length()==0)return null;
     if(str.length()==1)return str;
     return str.substring(1)+ str.charAt(0);
    }
}在实现上比较完美了。但是效率就留高手来解决了

下面方法时间复杂度O(N)【第二个循环长度不超过26的缘故】,且能找到所有“最长无重复字符子串”，实测有效package com.yuncong.qanda;import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;/**
* Largest No repeat son String.
* 最大无重复子串
*
* @author Jiang
*
*/
public class Question1 { public static void main(String[] args) { String s = null;
List<String> result = null;
s = "abcdefcght";
result = getLargestNoRptSon(s);
printAll(result);
} /**
*
* @param parent
*/
public static List<String> getLargestNoRptSon(String parent) {
List<String> rsCollection = new LinkedList<String>();
if (parent == null || parent.length() < 1)
return rsCollection;
// 初始化子串
int start = 0;
int end = 1;
boolean[] charAppear = new boolean[26];
int maxLength = 1;
// 遍历父串，每次遍历父串都更新最大无重复字符子串的索引位置
for (int i = end; i < parent.length(); i++) {
char ch = parent.charAt(i);
int chIndex = ch - 'a';
if (!charAppear[chIndex]) {
// 该字符未出现过
charAppear[chIndex] = true;
end++;
// 若到达父串的末端，则加入当前子串
if (end == parent.length()) {
int length = end - start;
maxLength = (length > maxLength) ? length : maxLength;
rsCollection.add(parent.substring(start, end));
}
} else {
// 字符已出现
int length = end - start;
maxLength = (length > maxLength) ? length : maxLength;
rsCollection.add(parent.substring(start, end)); int newStart = parent.indexOf(ch, start) + 1;
for (int j = start; j < newStart; j++) {
char ch1 = parent.charAt(j);
int chIndex1 = ch1 - 'a';
charAppear[chIndex1] = false;
}
start = newStart;
end++;
}
}
// 只保留最大长度的子串
for (Iterator<String> iter = rsCollection.iterator(); iter.hasNext();) {
String str = iter.next();
if (str.length() < maxLength)
iter.remove();
}
return rsCollection;
} public static void printAll(List<String> strings) {
System.out.println("----------------------");
for (Iterator<String> iter = strings.iterator(); iter.hasNext();) {
System.out.println(iter.next());
}
}}

package Lianxi;import java.util.HashSet;
import java.util.Iterator;public class LongStr {
public static void main(String[] args) {
String longsubstr="";
HashSet<String> s=new HashSet<String>();
String str="acbadfcbiufasbd";
System.out.println("原字符串："+str);

System.out.println("================================");
ok:
for(int i=0;i<str.length();i++){
char temp=str.charAt(i);
System.out.println(">"+temp);
for(int j=i+1;j<str.length();j++){
if(temp==str.charAt(j)){
String strsub=str.substring(i, j);
s.add(strsub);
System.out.println("无重复子字符串："+strsub);
break;
}
   if(j==str.length()-1){
   String strsub=str.substring(i,str.length());
   s.add(strsub);
   System.out.println("无重复子字符串："+strsub);
   break ok;
   }
}
}

System.out.println("================================");

Iterator<String> it =s.iterator();
while(it.hasNext()){
String strtemp=it.next();
if(strtemp.length()>longsubstr.length()){
longsubstr=strtemp;
}
}

System.out.println("最长无重复子字符串:"+longsubstr);
}}

调试易

优化-从输入的字符串中截取最长的没有重复字符的子串

解决方案 »