문제

문제 요약

문자열 s가 주어졌을 때 반복하는 문자가 없는 가장 긴 부분문자열의 길이를 구하시오

제약조건

• 문자열의 길이는 0 이상 50000 이하
• 문자열 s는 영문자, 숫자, 기호, 공백으로 구성

문제 접근

처음 문제를 보고 드는 생각은 DP로 풀면 문제가 풀릴 수 있을 거라고 생각해서, 점화식과 memoization 방법을 고민해 보았다. dp 점화식을 n 번째까지의 반복하는 문자 없는 가장 긴 문자열의 길이라고 가정하고, 시도했지만 반례가 존재하여 DP로는 못 풀었다.

문제를 해결한 방법으로는 슬라이딩 윈도우 알고리즘으로 풀었다. 슬라이딩 윈도우 알고리즘이란 배열이나 리스트에서 일정한 부분을 따로 분리하여 이를 문제의 조건과 만족하는 지 비교하며 윈도우의 크기를 조절하는 알고리즘이다.

1. start_point은 -1, end_point는 0인 크기가 1인 윈도우로 시작한다.
2. 문제에서 반복하는 문자가 존재하는 체크하여 반복하는 문자가 없다면 윈도우의 크기를 증가하고, 그렇지 않은 경우에는 start_point를 end_point로 옮긴 후에 윈도우의 크기를 증가시킨다.
3. 반복 문자 없는 가장 긴 길이의 부분문자열의 길이는 end_point - start_point 중 가장 큰 값을 취한다.

# Python3 소스
class Solution:
    class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    	# 중복 체크 및 문자의 위치 기록하기 위한 변수 charPos
        charPos = {}
        # 시작점을 -1로 설정
        start_point = -1
        answer = 0
        # end_point는 항상 증가하므로 for문의 변수로 설정
        for end_point in range(len(s)):
            if s[end_point] in charPos:
            	# 중복 문자가 등장한 경우 시작 위치를 원래의 start_point와 중복 문자가 이전에 등장한 위치 중에 더 큰 값으로 설정한다.
                start_point = max(start_point, charPos[s[end_point]])
            # s[end_point]의 위치를 end_point로 지정한다.
            charPos[s[end_point]] = end_point
            # 반복 문자 없는 가장 긴 부분문자열을 찾는다.
            answer = max(answer, end_point - start_point)
        return answer
            

// CPP 소스
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> pos;
        int answer = 0;
        int start = -1;
        for(int i=0; i < s.size(); i++){
            if (pos.count(s[i]) != 0){
//                 존재하는 경우
                start = max(start, pos[s[i]]);
            }
            pos[s[i]] = i;
            answer = max(answer, i - start);
        }
        return answer;
    }
};