3. Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

---

주어진 문자열에서 중복 없는, 연속된 문자열을 만들 때 가장 긴 문자열의 길이를 리턴하는 문제입니다.  medium 문제이지만, 크게 어렵지 않은 구현 문제입니다.

 

2중 for loop로 풀어보진 않았지만, 솔루션에 따르면 전부 다 탐색 해도 (brute-force) 풀수 있게 되어 있다고 합니다. 즉, 주어진 문자열을 다 순회하여서 중복이 있는지 없는지 확인해보며, 현재 길이가 가장 길게 갱신하면 됩니다. (하단 LeetCode solution 참조)

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }
}

---

제가 풀었던 방법은 반복문 하나만 써서 갱신해 나가는 방법이었습니다. (Sliding window)

문자열이 주어질 때 인덱스 두개 (i, j) 를 두어 중복이 없는 한에서 j 를 증가, 중복이 발생하면 i 를 증가시키는 방법입니다. 문자열 'abcabcd' 가 있다고 할 때 아래와 같이 진행됩니다.

(시작)
a b c a b c d
| |
i j

(j 증가)
a b c a b c d
|   |
i   j

(j 증가)
a b c a b c d
|     |
i     j

* 중복 발견 (i가 가르키는 문자와 j가 가르키는 문자가 같음)
이 때의 길이는 j - i + 1 과 같다. 이 값으로 정답과 비교, 최댓값으로 갱신

(i 증가 / j 를 i 다음에 위치)
a b c a b c d
  | |
  i j

 중복을 발견하는 방법으로는 자바의 Set 자료 구조를 사용하면 쉽게 구현할 수 있습니다.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }
        int result = 1;
        int i = 0;
        int j = 1;

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

시간 복잡도는 'ababab...' 와 같이 j 값이 증가할 수 없는 경우, 최대 O(n^2) 고 평균은 O(n) 이 될 것 같습니다.