문제

Given a string s, find the length of the longest substring without repeating characters.

제한사항

• 0 <= s.length <= $5 \cdot 10^4$
• s consists of English letters, digits, symbols and spaces.

접근

문자열이 주어졌을 때, 가장 긴 substring의 길이를 반환하는 문제입니다.

접근1

처음엔 투 포인터를 활용해서 substring을 만들어 중복여부를 체크하는 방식으로 접근했습니다만 문자열의 최대 길이가 50,000이었습니다. 투 포인터는 시간 복잡도가 $O(n^2)$라 시간 초과가 될 것이란 걸 간과했고, 중복 여부 로직이 최대 50,000이 될 수도 있는 것을 고려하면 매우 느린 접근이라는 것을 깨달았습니다.

답안1(시간 초과)

class Solution{
   public boolean IsWithoutRepeating(String str){
        boolean[] check = new boolean[128];

        for(int nIndex = 0 ; nIndex < str.length(); ++nIndex){
            char chr = str.charAt(nIndex);
            if(check[chr])
                return false;

            check[chr] = true;
        }
        return true;
    }

    public int lengthOfLongestSubstring(String s) {
        if(s.length() <= 1)
            return s.length();

        int answer = 0;

        for(int nLeft = 0 ; nLeft < s.length(); ++nLeft)
        {
            for(int nRight = s.length() - 1; nRight >= nLeft; --nRight){
                if(answer > nRight - nLeft)
                    break;

                String subStr = s.substring(nLeft, nRight + 1);
                if(IsWithoutRepeating(subStr))
                    answer = subStr.length();
            }
        }

        return answer;
    }
}

접근2

이번 문제는 로직이 떠오르지 않아 다른 분의 답안을 봤습니다. Set을 활용해 중복 여부를 체크한 방식이었습니다. 접근 방식은,

1. left, right 값을 각 0, 1로 시작
2. right 값이 Set에 없으며 left 값과 right 값이 같지 않다면, substring 내 중복된 문자가 없는 것이므로 Set에 Right 값을 추가하고 right - left + 1의 길이를 저장합니다.
   (물론 답이 되는 저장 변수 수보다 커야 합니다.)
3. 그 외, 중복된 문자가 있는 경우엔 Set을 초기화하고 left 값을 1 증가시키고 right 값을left+1로 초기화하여 substring 시작점을 초기화하고 다시 전개합니다.

이렇게 되면 기본 시간복잡도가 O(n)입니다. HashSet이라는 변수가 있었지만, 추가하는데 O(1)이므로 결과적으로 시간 복잡도가 O(n)입니다.

답안2

public Solution{

    public int lengthOfLongestSubstring(String s) {
        if(s.isEmpty())
            return 0;

        int answer = 1;
        int left = 0, right = 1;

        Set<Character> set = new HashSet<>();
        while(left < s.length() && right < s.length()){
            if(!set.contains(s.charAt(right)) && s.charAt(left) != s.charAt(right)){
                set.add(s.charAt(right));
                answer = Math.max(answer, right - left + 1);
                ++right;
            }
            else{
                set = new HashSet<>();
                ++left;
                right = left + 1;
            }
        }

        return answer;
    }
}

후기

오늘 LeetCode 풀이는 여기까지 하려고 합니다. 500문제를 푸는 것을 목표로 하고 있어 매주 4문제씩 푼다면 약 125주, 2년이 넘는 시간이 걸립니다.

직장도 있고 공부하는게 많아 더 속도를 낼 수 없다는게 다소 아쉽긴 하지만 그래도 꾸준히 해내고 있다는 사실에 자신감을 가지고 정진해야겠습니다.