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.
大致意思就是給定一個字符串s括堤，返回s的最長無重復(fù)字符子串的長度一也。
解決該題目最高效的方法是使用HashMap保存字符最近一次出現(xiàn)的位置。遍歷每個字符時添加它到一個已有的無重復(fù)字符子串結(jié)尾呜象，如果這個字符之前出現(xiàn)過恬叹，用HashMap查詢它出現(xiàn)的位置墓怀，如果它已經(jīng)在這個無重復(fù)字符子串中弹囚，更新子串的起點使這個字符加到子串末尾后仍保持無重復(fù)字符揉稚。通過這種方式秒啦，遍歷一次字符串，就可以得到所有的無重復(fù)字符子串搀玖，統(tǒng)計它們的長度選出最大的即可余境。
如果n為字符串的長度，m為字符的編碼范圍灌诅。
下面代碼的時間復(fù)雜度為O(n)芳来，空間復(fù)雜度為O(min(m, n)).
public class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> latestIndex = new HashMap<>(); // 存放字符最近一次出現(xiàn)的位置
int curStart = 0, curLen = 0, maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i); // 添加字符c到一個已有的無重復(fù)字符子串結(jié)尾
if (latestIndex.containsKey(c) && latestIndex.get(c) >= curStart) { // 字符c已經(jīng)在這個無重復(fù)字符子串中
curStart = latestIndex.get(c) + 1; // 更新當前無重復(fù)字符子串的起點
}
curLen = i - curStart + 1; // 當前無重復(fù)字符子串的長度
if (curLen > maxLen) {
maxLen = curLen;
}
latestIndex.put(c, i);
}
return maxLen;
}
}
如果已知字符編碼范圍很小，我們可以使用整型數(shù)組代替上面的HashMap
整型數(shù)組大小對應(yīng)的字符編碼范圍如下
-
int[26]for Letters 'a' - 'z' or 'A' - 'Z' -
int[128]for ASCII -
int[256]for Extended ASCII
下面代碼的時間復(fù)雜度為O(n)猜拾，空間復(fù)雜度為O(m).
public class Solution {
public int lengthOfLongestSubstring(String s) {
int[] latestIndex = new int[256]; // 存放字符最近一次出現(xiàn)的位置
for (int i = 0; i < 256; i++) {
latestIndex[i] = -1;
}
int curStart = 0, curLen = 0, maxLen = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i); // 添加字符c到一個已有的無重復(fù)字符子串結(jié)尾
if (latestIndex[c] >= curStart) { // 字符c已經(jīng)在這個無重復(fù)字符子串中
curStart = latestIndex[c] + 1; // 更新當前無重復(fù)字符子串的起點
}
curLen = i - curStart + 1; // 當前無重復(fù)字符子串的長度
if (curLen > maxLen) {
maxLen = curLen;
}
latestIndex[c] = i;
}
return maxLen;
}
}