int 배열이 주어지면 가장 긴 substring을 찾는 문제입니다.
단, substring안에 같은 letter이 들어가면 안됩니다.
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.
문제접근
이번에도 당연히 투포인터를 사용해 접근해야겠다고 생각했습니다.
그 이유는 substring인지 아닌지 O(n)번에 탐색하고 싶었기 때문입니다.
for loop를 2번 사용하여 탐색하는것보다 포인터를 2개사용하여 탐색할 수 있다고 판단하였습니다.
조건은 다음과 같습니다.
- Arraylist에 s[start]가 있다면 list의 0번째를 remove
- 만약 없다면 s[end]를 add
- end++
- max(max, list.size())
- 과정 반복
public int lengthOfLongestSubstring(String s) {
int max = 0;
int end = 0;
ArrayList<Character> list = new ArrayList<>();
while (end < s.length()) {
char cur = s.charAt(end);
if (list.contains(cur)) {
list.remove(0);
} else {
list.add(cur);
end++;
max = Math.max(max, list.size());
}
}
return max;
}
시간복잡도
end가 s.length()까지 반복하고있습니다.
그동안 ArrayList를 조건에 따라 contain, remove, add하고있습니다.
ArrayList의 add는 O(1)의 시간복잡도가 필요하지만, contain,remove는 O(n)의 시간복잡도가 필요합니다.
따라서 최악의경우 O(n2)의 시간복잡도가 필요합니다.
다른사람의 풀이
제 코드는 ArrayList를 사용하였지만 Set을 사용해서 문제를 푼 코드입니다.
Set은 add, remove, contain의 시간복잡도가 O(1)입니다.
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int maxLength = 0;
Set<Character> charSet = new HashSet<>();
int left = 0;
for (int right = 0; right < n; right++) {
if (!charSet.contains(s.charAt(right))) {
charSet.add(s.charAt(right));
maxLength = Math.max(maxLength, right - left + 1);
} else {
while (charSet.contains(s.charAt(right))) {
charSet.remove(s.charAt(left));
left++;
}
charSet.add(s.charAt(right));
}
}
return maxLength;
}
시간복잡도
위에 설명처럼 Set은 add, remove, contain의 시간복잡도가 O(1)입니다.
따라서 O(n)의 시간복잡도가 필요합니다.
느낀점
문제를 해결하면서 자료구조의 특성에따라 더 효율적인 코드를 작성할 수 있다는 것을 알게되었습니다.
상황에 따라 가장 최적의 자료구조를 선택해서 문제를 해결해야겠다는 생각이 들었습니다.
참고
'LeetCode' 카테고리의 다른 글
[LeetCode] 2. Add Two Numbers (1) | 2023.08.29 |
---|---|
[LeetCode] 141. Linked List Cycle (0) | 2023.08.28 |
[LeetCode] 209. Minimum Size Subarray Sum (0) | 2023.08.28 |
[LeetCode] 167. Two Sum II - Input Array Is Sorted (0) | 2023.08.27 |
[LeetCode] 125. Valid Palindrome (1) | 2023.08.27 |