Problem

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Understanding

采用分治策略读处，對于給定的串，滿足題設(shè)的子串(substring)要么在前半段唱矛，要么在后半段罚舱，要么跨越前后兩段，取其中的最大值即可绎谦。
關(guān)鍵問題是管闷，如何求取跨越其中兩段的最長子串。

求跨越兩段最長子串的策略

對于一個串s的兩個部分：left, right
為了求跨越left,right的最長滿足條件的子串, 首先left,right的相鄰邊界必須有字符并且不相同： left[-1], right[0], null 三者兩兩不相等窃肠。
其次包个，求解策略是，將令i指向left的尾部冤留，j指向right的首部碧囊， 如果對于某一個狀態(tài)i,j 總是嘗試將現(xiàn)有的最長串擴展到i-1,j+1的范圍顯然i-1,j+1所指向的字符如果已經(jīng)存在于當前的最長串中，則可以證明此時的指針已經(jīng)達到邊界纤怒。
循環(huán)不變式是：每次循環(huán)結(jié)束糯而，i,j必然包括最長的串，且i非遞增,j非遞減泊窘。所以在i,j的變化過程中所求得串長度一定是非遞減的熄驼。
循環(huán)結(jié)束的條件是i,j停止變化，因而當循環(huán)結(jié)束時能夠得到最長的串烘豹。

Code(Java)

import java.util.*;
public class LongestNoRepeat{

    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        //String s="qwekewre";
        System.out.println("input \"-\" to terminate");
        String s="-";
        while(in.hasNextLine() && !((s=in.nextLine()).equals("-")))
        {

            int[] res=findMost(s,0,s.length()-1);
            System.out.println("i,j,s[i...j]="+res[0]+","+res[1]+" : "+s.substring(res[0],res[1]+1));
        }
    }
        //返回int[]{i,j} 分別記錄開始和結(jié)束下標瓜贾，對于非空串，不會返回null
    public static int[] findMost(String s,int i,int j)
    {
        if(j-i==0)
            return new int[]{i,j};
        int mid=(j+i)/2;
        int[] s1=findMost(s,i,mid);
        int[] s2=findMost(s,mid+1,j);
        int x=mid,y=mid+1; 
        boolean xvalid=true,yvalid=true; //分別記錄左右指針是否還在變化

        int[] s0=null;
        if(s.charAt(x)!=s.charAt(y))
        {
            Set<Character> set=new HashSet<Character>();
            set.add(s.charAt(x));
            set.add(s.charAt(y));
            while(xvalid || yvalid)
            {
                        //循環(huán)不變式：每次循環(huán)開始時,  x,y必然指向當前最長的串
                      //每次循環(huán)結(jié)束時,  x非遞增變化, y非遞減變化
                        //且當x,y都不變化時携悯，循環(huán)退出
                if(xvalid)
                {
                    Character ch=null;
                    if(x==i)xvalid=false;
                    else if(set.contains(ch=s.charAt(x-1)))
                        xvalid=false;
                    else
                    {
                        x--;
                        set.add(ch);
                    }
                }

                if(yvalid)
                {
                    Character ch=null;
                    if(y==j)yvalid=false;
                    else if(set.contains(ch=s.charAt(y+1)))
                        yvalid=false;
                    else
                    {
                        y++;
                        set.add(ch);
                    }
                }
            }

            s0=new int[]{x,y};
        }
        int[] max=s0;
        if(max==null || max[1]-max[0]<s1[1]-s1[0])
            max=s1;
        if(max[1]-max[0] < s2[1]-s2[0])
            max=s2;

        return max;

    }
}