【leedcode】longest-substring-without-repeating-characters

时间:2023-01-12 18:31:34
Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is .

Given "bbbbb", the answer is "b", with the length of .

Given "pwwkew", the answer is "wke", with the length of . Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

寻找最长的不重复串,略像滑动窗口。

char[] buff;
//used
int used ;
public int lastIndexOf(char ch, int endIndex) {
int i = used;
for (; i >= endIndex; i--) {
if (buff[i] == ch) {
return i;
}
}
return -1;
}
public int lastIndexOf(char ch) {
return lastIndexOf(ch, 0);
} public int lengthOfLongestSubstring(String s) {
if (s == null || s.isEmpty()) {
return 0;
}
int len = s.length();
buff = new char[len];
buff[0] = s.charAt(0);
used = 1;
char t;
int idx = -1;
int top = 0;
int first = 0;
while(used<len){
t = s.charAt(used);
idx = lastIndexOf(t, first);
// System.err.println("["+top+"]s=" + new String(buff) + "," + (idx>-1 ? ( "pos=" + idx + " find " + t ) : "" ) + ",idx=" + used + ",first=" + first); if (idx > -1) {
top = Math.max(used - first, top);
first = idx+1;
} buff[used] = t;
used++;
} // System.err.println("["+top+"]s=" + new String(buff) + "," + (idx>-1 ? ( "pos=" + idx + " find " + t ) : "" ) + ",idx=" + used + ",first=" + first);
return Math.max(len - first, top);
}

上面这个粗鲁的代码,马马虎虎毕竟打败51 ~61%的code,lastIndexOf有优化的空间。

不过答案真是美妙的活动窗口实现,赞!使用了字符作为坐标,索引作为值。

 public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}