๐ ๋ฌธ์
Given a string s, find the length of the longest substring without repeating characters.
๐ ๋ฐฉ๋ฒ
- ์ปฌ๋ ์ ์ ์ด์ฉํ์ฌ ํ์ด
- ๊ทธ ์ค์์ Set์ HashSet์ ์ด์ฉํ์ฌ ํ์ด
1๏ธโฃ ์ต๋๊ฐ max ์ ์ธ ๋ฐ ์ด๊ธฐํ
2๏ธโฃ HashSet์ ์ด์ฉํ์ฌ ํ์ด
3๏ธโฃ ์์ ๋ณ์๊ณผ ๋๋๋ ๋ณ์ ์ ์ธ ๋ฐ ์ด๊ธฐํ
4๏ธโฃ while ๋ฌธ์ผ๋ก ํ์ด (O(n)์ ๋ณต์ก๋๋ก ํ์ด)
5๏ธโฃ ๋ฌธ์์ด์ ๋ฌธ์๋ฅผ ํ๋์ฉ ์ฐจ๋ก๋ก ๋น๊ต
6๏ธโฃ ์กฐ๊ฑด๋ฌธ์ ์ด์ฉํ์ฌ set์ ์กด์ฌํ์ง ์์ผ๋ฉด set์ ๋ฃ์ด์ฃผ๊ณ end ๊ฐ ++
7๏ธโฃ ๋ - ์์ ๋บ ๊ฐ์ ๊ตฌํด ๊ทธ ์ค์์ max ๊ฐ์ ๊ตฌํ๊ธฐ
8๏ธโฃ ๋ง์ฝ set์ ์กด์ฌํ๋ฉด ์์์ ์ ๋ฌธ์ ์ง์ฐ๊ธฐ
import java.util.HashSet;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<>();
/* ๋ฐํํ ์ต๋ ๊ฐ ์ด๊ธฐํ */
int max = 0;
int start = 0;
int end = 0;
while (end < s.length()) {
if (start > end) {
break;
}
if (!set.contains(s.charAt(end))) {
set.add(s.charAt(end++));
max = Math.max(max, end - start);
continue;
}
set.remove(s.charAt(start++));
}
return max;
}
}
'์๊ณ ๋ฆฌ์ฆ > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[LeetCode]006. Zigzag Conversion JAVA (0) | 2022.12.21 |
---|---|
[LeetCode]007. Reverse Integer JAVA (0) | 2022.12.19 |
[LeetCode]005. Longest Palindromic Substring JAVA (0) | 2022.12.19 |
[LeetCode] 002. Add Two Numbers JAVA (0) | 2022.12.16 |
[LeetCode] 001. Two Sum JAVA (0) | 2022.12.15 |
๋๊ธ