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
- Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
- Set java类型 TreeSet HashSet
暴力法
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i; j <= s.length(); j++) {
if (isUnique(s, i, j)) {
ans = Math.max(j - i, ans);
}
}
}
return ans;
}
public boolean isUnique(String s, int i, int j) {
Set<Character> chSets = new HashSet<>();
for (int z = i; z < j; z++) {
Character ch = s.charAt(z);
if (chSets.contains(ch)) return false;
chSets.add(ch);
}
return true;
}
}
时间复杂度O(n3)
划窗口法
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0;
int n = s.length();
int ans = 0;
Set<Character> chSets = new HashSet<>();
while (i < n && j < n) {
if (!chSets.contains(s.charAt(j))) {
chSets.add(s.charAt(j++));
ans = Math.max(j-i, ans);
}
else {
chSets.remove(s.charAt(i++));
}
}
return ans;
}
时间复杂度: O(2n)
空间复杂度: O(min(m, n))
opt sliding
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0;
Map<Character, Integer> chMaps = new HashMap<>();
for (int i = 0, j = 0; j < n; j++) {
if (chMaps.containsKey(s.charAt(j))) {
i = Math.max(i, chMaps.get(s.charAt(j)));
}
ans = Math.max(ans, j - i + 1);
chMaps.put(s.charAt(j), j + 1);
}
return ans;
}
滑窗口时 i 也会遍历n, 遇到想重复的char , i 直接跳到 临近重复的下一个,避免遍历。