[Leetcode] 3. Longest Substring Without Repeating Characters

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

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.

Example 4:

Input: s = ""
Output: 0

sliding window 방식으로 풀수 있다.

 

1. 두개의 포인터 i,j 를 두고 기본적으로 길이를 벌려 나가면서 중복을 체크한다.
2. 만약 중복된 데이터가 체크된다면, sliding window 방식으로 왼쪽의 포인터를 하나 앞으로 당기고 반복한다.
3. 2번을 수행할때 오른쪽 포인터를 다시 좁힐 필요는 없다. 왜냐하면 이미 i,j 사이의 값들은 중복이 없다고 검사가 된 상태이기 때문에, i를 하나 좁혔다 하더라도 사이의 값들은 여전히 중복이 없는 상태이기 때문이다.

이 경우 시간복잡도는 O(N) 이 된다. 아래 코드는 내가 푼 코드이다.

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

public class LongestSubstringWithoutRepeatingCharacters {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;

        int i = 0;
        int j = 0;

        Set<Character> cache = new HashSet<>();

        while (j < s.length()) {
            char ch = s.charAt(j);

            if (cache.contains(ch) == false) {
                cache.add(ch);
                max = Math.max(max, j - i + 1);
                j++;
            } else {

                cache.remove(s.charAt(i));
                i++;
            }
        }

        return max;
    }
}