[알고리즘] LeetCode - Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters - LeetCode

문제 설명

• 영문자, 숫자, 공백으로 구성된 문자열 s가 주어진다.
• s에서 알파벳이 중복되지 않고 가장 긴 부분 문자열의 길이를 반환해야 한다.

문제 해결

• 윈도우 크기를 점점 늘려가면서 탐색을 진행하다가, 부분 문자열에 있는 문자와 중복된 문자를 만나면 부분 문자열에서 중복된 문자 바로 다음의 문자부터 끝 문자까지 분리한다.
• 매 반복마다 윈도우 크기 값을 정수형 변수 answer에 최댓값 갱신한다.
• substring을 이용해서 분리하는 코드를 간소화했다.
• indexOf를 통해 중복된 문자의 여부를 확인하고 위치를 파악했다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int N = s.length();
        char[] arr = s.toCharArray();
        String sub = "";
        int answer = 0;

        for (int i = 0; i < N; i++) {
            char now = arr[i];
            int idx = sub.indexOf(now);
            if (idx >= 0) {
                sub = sub.substring(idx + 1);
            }
            sub += now;
            answer = Math.max(answer, sub.length());
        }

        return answer;
    }
}

결과

시간	메모리
11 ms	44.9 MB