Given a string s
, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Example 4:
Input: s = ""
Output: 0
Constraints:
0 <= s.length <= 5 * 104
s
consists of English letters, digits, symbols and spaces.
sliding window 기법으로 풀 수 있다. 기본적으로는 right point 를 하나씩 늘려나가면서, 만약 중복된 character 를 만나게 되면 중복된 character 가 제거될때까지 left point 를 하나씩 당겨준다.
아래 두개의 코드는 시간 복잡도는 동일하다.
아래 코드에서도 while 문 하나만 도는 것 같지만 .. 자세히 보면 left 가 당겨질때 right 는 당겨지지 않으므로 loop 의 총 도는 횟수는 동일하다.
// 최근에 푼 코드
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int max = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char ch = s.charAt(right);
// if we find duplicate character, then we will pull left into right
while (set.contains(ch) && left <= right) {
max = Math.max(max, right - left);
set.remove(s.charAt(left));
left++;
}
set.add(ch);
}
return Math.max(max, set.size());
}
// 예전에 푼 코드
class Solution {
public int lengthOfLongestSubstring(String s) {
int max = 0;
int i = 0;
int j = 0;
Set<Character> cache = new HashSet<>();
while (j < s.length()) {
char ch = s.charAt(j);
if (cache.contains(ch) == false) {
cache.add(ch);
max = Math.max(max, j - i + 1);
j++;
} else {
cache.remove(s.charAt(i));
i++;
}
}
return max;
}
}
'Algorithm' 카테고리의 다른 글
[leetcode] 573. Squirrel Simulation (0) | 2021.02.03 |
---|---|
134. Gas Station (0) | 2021.01.24 |
[Leetcode] 443. String Compression (0) | 2020.12.28 |
[Leetcode] 1197. Minimum Knight Moves (0) | 2020.12.26 |
1283. Find the Smallest Divisor Given a Threshold (0) | 2020.12.26 |