[알고리즘] Longest Substring Without Repeating Characters

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

https://leetcode.com/problems/longest-substring-without-repeating-characters/

 

문자열에서 반복되지 않는 문자가 나오기전까지 문자열의 갯수를 세는 것입니다.

 

첫번째 도전은 다음과 같이 했습니다.

class Solution {
  int lengthOfLongestSubstring(String s) {
    if (s.length == 1) return 1;
    List<String> list = [];
  
    int count = 0;
    for (int i =0; i<s.length; i++) {
      for (int j = i; j < s.length; j++) {
        if (list.contains(s[j])) {
          if (list.length > count) {
            count = list.length;
          }
          list.clear();
          break;
        }

        list.add(s[j]);
      }
    }

    return count;
    
  }
}

 

당연하게 이중 for문을 구현했을때는 시간이 많이 걸릴것이라고 생각했습니다. 그러나 일단 동작 여부를 확인하니 동작이 되었습니다.

 

 

슬라이딩 윈도우 라는 형태의 알고리즘 방법을 활용한 풀이 방법이며,

해당 방법은 O(n^2) 으로 걸릴 문제를 O(n) 으로 최적화할 수 있는 방법입니다.

포인터 2개를 활용해서 윈도우(영역)의 시작과 끝 영역을 잡고 조건이 충족되지 않는다면 윈도우가 증가하고 조건이 충족하면 윈도우가 줄어드는 형태입니다.

 

예를 들어서 다음과 같은 문제들에 슬라이딩 윈도우를 사용할 수 있습니다.

- "연속된 3일 동안의 주식 가격 합이 가장 높은 구간은?"

- "길이가 N인 배열에서 연속된 k개 숫자의 합이 가장 큰 경우를 찾아라."

- "문자열에서 문자가 중복되지 않는 가장 긴 부분 문자열의 길이를 구하라"(위의 문제)

- "연속된 부분 배열의 합이 특정 값 이상이 되는 경우 중, 길이가 가장 짧은 것을 찾아라"

 

class Solution {
  int lengthOfLongestSubstring(String s) {
    Map<String, int> charIndexMap = {};
    int maxLength = 0;
    int left = 0;

    for (int right = 0; right < s.length; right++) {
      String currentChar = s[right];

      if (charIndexMap.containsKey(currentChar)) {
        int prevIndex = charIndexMap[currentChar]!;
        if (prevIndex >= left) {
          left = prevIndex + 1;
        }
      }
      charIndexMap[currentChar] = right;

      int currentLength = right - left + 1;
      if (currentLength > maxLength) {
        maxLength = currentLength;
      }
    }

    return maxLength;
  }
}

 

슬라이딩 윈도우 형태로 문제를 풀 경우에 속도가 확 줄어드는 것을 알 수 있습니다.