[LeetCode] 3. Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode

 

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개사용하여 탐색할 수 있다고 판단하였습니다.

 

조건은 다음과 같습니다.

1. Arraylist에 s[start]가 있다면 list의 0번째를 remove
2. 만약 없다면 s[end]를 add
   
   • end++
   • max(max, list.size())
3. 과정 반복

    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)의 시간복잡도가 필요합니다.

 

 

느낀점

문제를 해결하면서 자료구조의 특성에따라 더 효율적인 코드를 작성할 수 있다는 것을 알게되었습니다.

상황에 따라 가장 최적의 자료구조를 선택해서 문제를 해결해야겠다는 생각이 들었습니다.

 

참고

Longest Substring Without Repeating Characters - LeetCode