Description
Given a string, find the length of the longest substring without repeating characters.
Samples
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.
Solutions
<ol>
<li> O(n)
public class A0003_Longest_Substring_Without_Repeating_Characters {
public static void main(String[] args) {
Map<String, Integer> samples = new HashMap<String, Integer>() {
{
put("abcabcbb", 3);
put("bbbb", 1);
put("pwwkew", 3);
put("abba", 2);
}
};
for (String string : samples.keySet()) {
assert solution1(text) == samples.get(text);
}
}
/**
* O(n)
* 將字符串的字符作為鍵控汉，其坐標(biāo)作為值存在map中岩灭。使用left和right兩個指針代表最大不重復(fù)子串的坐標(biāo)，則最大長度為right-left+1.
* right不斷向后遍歷玄柏，當(dāng)發(fā)現(xiàn)存在于map中的字符時纬傲，更新left的值為上個相同字符的下一坐標(biāo)满败，因為這樣可以保證子串的字符是互不相同的
* @return
*/
public static int solution1(String text) {
if (text == null || text.length() == 0) return 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
// include left and right
for (int right = 0, left= 0; right < text.length(); right++) {
if (map.containsKey(text.charAt(right))) {
left = Math.max(left, map.get(text.charAt(right)) + 1);
}
map.put(text.charAt(right), right);
max = Math.max(max, right - left + 1);
}
return max;
}
}
