無重復(fù)字符的最長子串
給定一個(gè)字符串，請你找出其中不含有重復(fù)字符的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個(gè)子序列，不是子串。
首先分析一下題目，求給定字符串的最長不重復(fù)子串，思路應(yīng)該是分治不斷降規(guī)模，把長度為n的字符串降為n-1的字符串的最長不重復(fù)子串，然后到n-2，.... 直到規(guī)模為1，關(guān)鍵在于如何得到遞推式。
以pwwkew為例做初步分析 ，定義a[i][j]為子串s[i,j]的最長不重復(fù)子串，容易得出以下結(jié)論:
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）多一個(gè)字符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，什么時(shí)候是1，第一感覺是s(i,j-1)不含字符s(j)的時(shí)候。
不過這個(gè)感覺是錯(cuò)的，比如pwwk，a[0][2]= len（pww）=2； s（0，2）不含s（3）也就是字符k，a[0][3]= len（pwwk）為2 。
進(jìn)一步分析，f（j）= 1時(shí)，要具備一個(gè)條件，也就是s[i,j-1]的最長子串出現(xiàn)的位置必須是緊挨j的位置，
比如pwwk， s(0,2)出現(xiàn)最長子串是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; 因?yàn)榫o挨s（4）也就是字符e的wk剛好也是s（0，3）的最長子串。
關(guān)于計(jì)算順序，先計(jì)算單個(gè)字符，然后2個(gè)字符，然后3個(gè)字符,.... n個(gè)字符的最長子串。
根據(jù)上面分析，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，平臺(tái)提交一下.....??超出內(nèi)存限制（98/100）,通過了97個(gè)用例，第98是一個(gè)幾頁紙長的一個(gè)字符串。
代碼使用了n*n的int數(shù)組保存中間計(jì)算結(jié)果(n為字符串長度)，當(dāng)n非常大的時(shí)候.....
好吧，想辦法減一點(diǎn)內(nèi)存消耗。
其實(shí)二維數(shù)組有將近一半沒有使用，真正用到的只有矩陣A[i,j]的(j>i部分)的半個(gè)矩陣
如pwwke的計(jì)算過程和結(jié)果如下，箭頭表示計(jì)算過程，從長到短。
矩陣的左下全都沒用，這個(gè)應(yīng)該算是稀疏矩陣吧，大學(xué)時(shí)期學(xué)好像有聽過稀疏矩陣的壓縮存儲(chǔ)，不管了，很遙遠(yuǎn)了，嘗試用一維數(shù)組來存儲(chǔ)這矩陣，數(shù)組的長度為 n + (n-1) + ... + 1 = n*(n+1)/2 ，比 n ^2還是省很多了。
接下來就是坐標(biāo)換算了, 二維的坐標(biāo)換到一維
(i,j )---> index
求index（i,j）的表達(dá)式。
對照上面的圖 （i為行數(shù)，j為列數(shù)）
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 時(shí)也滿足。
好了，修改代碼，把算法中的二維數(shù)組變成一維，修改后代碼如下
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;
}
這下應(yīng)該行了吧，......... 生活總是殘酷的，很多時(shí)候，努力了也不一定會(huì)有好的結(jié)果，還是超出內(nèi)存限制。
看來得換另外的方式了，二維數(shù)組內(nèi)存消耗太大了，盡管改成了一維，但本質(zhì)上還是二維，那就來個(gè)真正的一維吧。
一頓分析猛如虎......
定義a[j]為 s（0，j）的最長子串， 真一維了，a[n-1] 為題目所求。
a[j] 與 a[j-1]的遞推式跟上面一致，關(guān)鍵也是s（0，j-1）的最長子串是以j-1結(jié)尾的
s(0,j-1) 的最長子串長度為 max，如果s(j-max, j-1)這段長度為max的子串是s（0，j-1）的最長子串，即s(j-max, j-1)沒有重復(fù)字符，而且如果s(j-max, j-1)不含字符s（j），則s(j-max, j) 是 s（0，j）的最長子串
那關(guān)鍵問題就是要判斷s(j-max, j-1) 這一小段有沒有重復(fù)了，s(j-max, j-1)有沒有包含字符s[j]了，這個(gè)好說，弄一個(gè)HashSet來協(xié)助判斷。
通過上面分析，形成新的代碼如下
int []a;// a[i] 標(biāo)示 s[0,i]的最大不重復(fù)子串長度
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;
}
這次提交通過了。
以上是筆者對這道理整個(gè)思考和解答過程，權(quán)且記錄。
