无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

首先分析一下题目，求给定字符串的最长不重复子串，思路应该是分治不断降规模，把长度为n的字符串降为n-1的字符串的最长不重复子串，然后到n-2，.... 直到规模为1，关键在于如何得到递推式。

以pwwkew为例做初步分析 ，定义a[i][j]为子串s[i,j]的最长不重复子串，容易得出以下结论:

a[0][0] = len(p) = 1;

a[0][1] = len(pw) = 2;

a[1][2] = len(ww) = 1;

a[i][i] = 1;

字符串s（i，j）包含s（i，j-1）并且只比s（i，j-1）多一个字符s[j],

定义a[i][j] = a[i][j-1] + f(j);

a[i][j] 要么和a[i][j-1]相等，要么比a[i][j-1]多1，

f（j）返回值只能是0或者1，什么时候是1，第一感觉是s(i,j-1)不含字符s(j)的时候。

不过这个感觉是错的，比如pwwk，a[0][2]= len（pww）=2； s（0，2）不含s（3）也就是字符k，a[0][3]= len（pwwk）为2 。

进一步分析，f（j）= 1时，要具备一个条件，也就是s[i,j-1]的最长子串出现的位置必须是紧挨j的位置，

比如pwwk， s(0,2)出现最长子串是pw，而不是ww，a[0][3] != a[0][2] + 1;

再比如pwwke, s（0，3）最长子串是pw或者wk，s（0，4）为wke, a[0][4] = a[0][3] + 1; 因为紧挨s（4）也就是字符e的wk刚好也是s（0，3）的最长子串。

关于计算顺序，先计算单个字符，然后2个字符，然后3个字符,.... n个字符的最长子串。

根据上面分析，code如下

class Solution {
    int[][] a;
    int n;

    public int lengthOfLongestSubstring(String s) {
        // a[i,j] 定义为s[i,j]的最长子串的长度
        // a[i,j] = a[i,j-1] + s[i,j-1].contain(s[j]) ? 0 :1,

        n = s.length();
        a = new int[n][n];
        for (int i = 0; i < n; i++) {
            a[i] = new int[n];
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                a[j][j + i] = maxLength(s, j, j + i);
                if(max < a[j][j + i]){
                    max = a[j][j + i];
                }
            }
        }
        return max;
    }

    public int maxLength(String s, int i, int j) {
        if (i == j)
            return 1;
        return  contain(s, i, j - 1, j) + a[i][j - 1];

    }

    int max(int a, int b) {
        return a > b ? a : b;
    }

    int contain(String s, int l, int h, int z) {
        char ch = s.charAt(z);
        int maxLen = a[l][h];
        if(a[h-maxLen+1][h] == maxLen){
            for (int i = h; i >= h - maxLen+1; i--) {
                if (s.charAt(i) == ch) {
                    return 0;
                }
            }
            return 1;
        }
        return 0;      
    }
}

满心欢喜，折腾了半天终于完工了，拿来测试用例也都OK，平台提交一下.....😭超出内存限制（98/100）,通过了97个用例，第98是一个几页纸长的一个字符串。

代码使用了n*n的int数组保存中间计算结果(n为字符串长度)，当n非常大的时候.....
好吧，想办法减一点内存消耗。

其实二维数组有将近一半没有使用，真正用到的只有矩阵A[i,j]的(j>i部分)的半个矩阵

如pwwke的计算过程和结果如下，箭头表示计算过程，从长到短。

pwwke的计算过程和结果

矩阵的左下全都没用，这个应该算是稀疏矩阵吧，大学时期学好像有听过稀疏矩阵的压缩存储，不管了，很遥远了，尝试用一维数组来存储这矩阵，数组的长度为 n + (n-1) + ... + 1 = n*(n+1)/2 ，比 n ^2还是省很多了。

接下来就是坐标换算了, 二维的坐标换到一维
(i,j )---> index

求index（i,j）的表达式。
对照上面的图 （i为行数，j为列数）
index（i，j） = index(i,i) + j-i; // 先定位到第i行对角线位置，再偏移j-i
index（i, i）= n + (n-1) +...(n-i+1) = (2n-i+1) /2
index(i, j) = (2n-i+1) /2 + j-i

合并一下

index(i, j) =  i*(2n-1-i)/2 + j 

i = 0 时也满足。

好了，修改代码，把算法中的二维数组变成一维，修改后代码如下

int[] a;
int n;
int twoN_1; // 2n-1

public int lengthOfLongestSubstring(String s) {
    // a[i,j] 定义为s[i,j]的最长子串的长度
    // a[i,j] = a[i,j-1] + s[i,j-1].contain(s[j]) ? 0 :1,

    n = s.length();
    twoN_1 = 2*n -1;
    a = new int[n*(n+1)/2];
 
    //    j ---->
    // i  00 01 02 03 04
    // |  10 11 12 13 14
    // !  20 21 22 23 24
    // !  30 31 32 33 34 
    //    40 41 42 43 44
    // a[b][c] --> a[index];
    // index = i*(2n-1-i)/2 + j
    int max = 0;
    int tmpIndex = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            tmpIndex = index(j,j+i);
            a[tmpIndex] = maxLength(s, j, j + i);
            if(max < a[tmpIndex]){
                max = a[tmpIndex];
            }
        }
    }
    return max;
}

public int index(int i,int j){
    return i * (twoN_1 -i) /2 +j;
}

public int maxLength(String s, int i, int j) {
    if (i == j)
        return 1;
    return  contain(s, i, j - 1, j) + a[index(i,j-1)];

}

int max(int a, int b) {
    return a > b ? a : b;
}

int contain(String s, int l, int h, int z) {
    char ch = s.charAt(z);
    int maxLen = a[index(l,h)];
    if(a[index(h-maxLen+1,h)] == maxLen){
        for (int i = h; i >= h - maxLen+1; i--) {
            if (s.charAt(i) == ch) {
                return 0;
            }
        }
        return 1;
    }
    return 0;      
}

这下应该行了吧，......... 生活总是残酷的，很多时候，努力了也不一定会有好的结果，还是超出内存限制。

看来得换另外的方式了，二维数组内存消耗太大了，尽管改成了一维，但本质上还是二维，那就来个真正的一维吧。

一顿分析猛如虎......

定义a[j]为 s（0，j）的最长子串， 真一维了，a[n-1] 为题目所求。

a[j] 与 a[j-1]的递推式跟上面一致，关键也是s（0，j-1）的最长子串是以j-1结尾的

s(0,j-1) 的最长子串长度为 max，如果s(j-max, j-1)这段长度为max的子串是s（0，j-1）的最长子串，即s(j-max, j-1)没有重复字符，而且如果s(j-max, j-1)不含字符s（j），则s(j-max, j) 是 s（0，j）的最长子串

那关键问题就是要判断s(j-max, j-1) 这一小段有没有重复了，s(j-max, j-1)有没有包含字符s[j]了，这个好说，弄一个HashSet来协助判断。

通过上面分析，形成新的代码如下

int []a;// a[i] 标示 s[0,i]的最大不重复子串长度
int n;
public int lengthOfLongestSubstring(String s) {
    n = s.length();
    a = new int[n];
    if(n == 0) return 0;
    a[0] = 1;
    for(int i=1;i<n;i++){
        a[i] = a[i-1] + fun(s,i);
    }
    return a[n-1];
}

HashSet<Character> hs = new HashSet();
// pwwk e  1 2 2 2
int fun(String s,int i){ // 返回0 || 1
    int h = i-1;
    int maxLen = a[h];
  
    char tmp;
    hs.clear();
    for(int j=h-maxLen+1 ;j<=h;j++){
        tmp = s.charAt(j);
        if(hs.contains(tmp))
           return 0;
        else hs.add(tmp);
    }

    return hs.contains(s.charAt(i)) ? 0 : 1;
}

这次提交通过了。

以上是笔者对这道理整个思考和解答过程，权且记录。