Given a string, find the length of the longest substring without repeating characters.
Example
- For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.
- For "bbbbb" the longest substring is "b", with the length of 1.
思路
Hashtable：for character occurrence叙淌。
int[256]全部初始化為1-
Two Pointers: one points to the first character of a substring, and the other one points to the last character of the substring.
- 當(dāng)發(fā)現(xiàn)雙指針之間的沒(méi)有重復(fù)的字符時(shí)，右指針右移愁铺，加入一個(gè)字母鹰霍，
int[256]對(duì)應(yīng)位置-1。判斷：int[256]是否存在-1茵乱，不存在茂洒，說(shuō)明沒(méi)有重復(fù)字符，更新maxLen且 右指針繼續(xù)右移似将。 - 當(dāng)發(fā)現(xiàn)雙指針之間的有重復(fù)的字符時(shí)获黔，左指針右移，移除一個(gè)字符在验，
int[256]對(duì)應(yīng)位置+1玷氏。判斷：int[256]是否存在-1，存在腋舌，則繼續(xù)右移左指針盏触，直到不存在重復(fù)為止。 -
重復(fù)以上過(guò)程块饺，直到遍歷完成赞辩。
image.png
- 當(dāng)發(fā)現(xiàn)雙指針之間的沒(méi)有重復(fù)的字符時(shí)，右指針右移愁铺，加入一個(gè)字母鹰霍，
需一個(gè)global變量maxLen，記錄當(dāng)前不重復(fù)字母substring的最長(zhǎng)值授艰。
Time: O(n), Space: O(1)
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLen = Integer.MIN_VALUE;
int sLen = s.length();
if (sLen == 0)
{
return 0;
}
int[] tracker = new int [256];
Arrays.fill (tracker, 1);
int left = 0;
int right = 0;
while (right < sLen)
{
tracker [s.charAt(right)] --;
if (!hasNegativeEntry (tracker))
{
int len = right - left + 1;
maxLen = Math.max(len, maxLen);
}
while (hasNegativeEntry (tracker))
{
tracker [s.charAt(left)] ++;
left++;
}
right ++;
}
return maxLen;
}
public boolean hasNegativeEntry (int[] tracker)
{
for (int entry : tracker)
{
if (entry < 0)
{
return true;
}
}
return false;
}
}
