본문 바로가기

Algorithm

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

Constraints:

  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

sliding window 기법으로 풀 수 있다. 기본적으로는 right point 를 하나씩 늘려나가면서, 만약 중복된 character 를 만나게 되면 중복된 character 가 제거될때까지 left point 를 하나씩 당겨준다.

아래 두개의 코드는 시간 복잡도는 동일하다.

아래 코드에서도 while 문 하나만 도는 것 같지만 .. 자세히 보면 left 가 당겨질때 right 는 당겨지지 않으므로 loop 의 총 도는 횟수는 동일하다.

// 최근에 푼 코드
public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int max = 0;

        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);

            // if we find duplicate character, then we will pull left into right
            while (set.contains(ch) && left <= right) {
                max = Math.max(max, right - left);
                set.remove(s.charAt(left));
                left++;
            }

            set.add(ch);
        }

        return Math.max(max, set.size());
    }
// 예전에 푼 코드
class Solution {
    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;
    }
}

'Algorithm' 카테고리의 다른 글