Longest Substring Without Repeating Characters
Total Accepted: 152787 Total
Submissions: 687012 Difficulty: Medium
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.
Subscribe to see which companies asked this question
Hide Tags
Hash Table Two
Pointers String
Hide Similar Problems
(H) Longest Substring with At Most Two Distinct Characters
思路:
保护1个HashMap存储每一个字符的位置;两个指针i,j,保护最长子串的范围。
java code:
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null || s.length()==0) return 0;
Map<Character, Integer> map = new HashMap<Character, Integer>();
int max = 0;
for(int i=0,j=0;i<s.length();i++) {
char c = s.charAt(i);
if(map.containsKey(c)) {
j = Math.max(j, map.get(c)+1);
}
map.put(c, i);
max = Math.max(max, i-j+1);
}
return max;
}
}