주어진 문자열에서 반복되는 문자가 없는 가장 긴 부분 문자열의 길이를 찾는 알고리즘 문제입니다. 예를 들어, "abcabcbb"의 경우 중복 문자가 없는 가장 긴 부분 문자열은 "abc"이며 길이는 3입니다. "bbbbb"의 경우 가장 긴 부분 문자열은 "b"이고 길이는 1입니다.

접근 방법 1: 고정 크기 배열을 활용한 슬라이딩 윈도우

이 방법은 고정 크기 배열(예: ASCII 문자셋을 위한 256 크기 배열)을 사용하여 현재 슬라이딩 윈도우 내에 각 문자의 존재 여부를 추적합니다. 두 개의 포인터, leftPointer와 rightPointer를 사용하여 윈도우의 시작과 끝을 정의합니다.

• rightPointer를 문자열의 시작부터 끝까지 한 칸씩 이동합니다.
• rightPointer가 가리키는 문자가 이미 윈도우 내에 있다면 (배열에 true로 표시되어 있다면), leftPointer를 이동시켜 해당 중복 문자를 윈도우 밖으로 제거합니다. 이 과정은 중복 문자가 더 이상 없을 때까지 반복됩니다.
• 중복 문자가 처리된 후, rightPointer가 가리키는 문자를 윈도우에 추가하고 배열에 true로 표시합니다.
• 매 단계마다 현재 윈도우의 길이(rightPointer - leftPointer + 1)를 계산하고 최대 길이를 업데이트합니다.

#include <string>
#include <vector>
#include <algorithm> // std::max를 위해

class Solution {
public:
    int findMaxUniqueSubstringLength(const std::string& inputStr) {
        std::vector<bool> charExistence(256, false); // ASCII 문자셋을 위한 배열
        int currentMax = 0;
        int leftPointer = 0;

        for (int rightPointer = 0; rightPointer < inputStr.length(); ++rightPointer) {
            // 현재 문자가 윈도우 내에 이미 존재한다면
            while (charExistence[inputStr[rightPointer]]) {
                // 중복 문자가 없어질 때까지 leftPointer 이동 및 배열에서 제거
                charExistence[inputStr[leftPointer]] = false;
                leftPointer++;
            }
            // 현재 문자를 윈도우에 추가하고 존재 여부를 true로 설정
            charExistence[inputStr[rightPointer]] = true;
            // 현재 윈도우의 길이와 최대 길이 비교 및 업데이트
            currentMax = std::max(currentMax, rightPointer - leftPointer + 1);
        }
        return currentMax;
    }
};

접근 방법 2: std::unordered_set을 활용한 슬라이딩 윈도우

std::unordered_set은 요소의 삽입, 삭제, 검색을 평균적으로 O(1) 시간에 수행하므로, 윈도우 내에 유니크한 문자 집합을 효율적으로 관리할 수 있습니다. 이 방법도 두 개의 포인터, windowStart와 windowEnd를 사용합니다.

• windowEnd 포인터를 문자열을 따라 이동시키면서 새로운 문자를 검사합니다.
• 새 문자가 std::unordered_set에 없다면, 이를 셋에 추가하고 현재 윈도우의 길이를 업데이트합니다.
• 새 문자가 셋에 이미 있다면, 이는 중복 문자가 발견되었다는 의미입니다. 이 경우 windowStart를 이동시키면서 셋에서 문자를 제거합니다. 이 과정은 중복된 문자가 셋에서 제거될 때까지 진행됩니다.
• 중복 문자를 셋에서 제거한 후, windowStart와 windowEnd 포인터를 한 칸씩 전진시켜 다음 탐색을 준비합니다.

#include <string>
#include <unordered_set>
#include <algorithm> // std::max를 위해

class Solution {
public:
    int calculateLongestUniqueSubstring(const std::string& s) {
        if (s.empty()) {
            return 0;
        }

        int windowStart = 0;
        int windowEnd = 0;
        int longestLength = 0;
        std::unordered_set<char> uniqueWindowChars;

        while (windowEnd < s.length()) {
            if (uniqueWindowChars.find(s[windowEnd]) == uniqueWindowChars.end()) {
                // 현재 문자가 윈도우에 없음: 추가하고 윈도우 확장
                uniqueWindowChars.insert(s[windowEnd]);
                longestLength = std::max(longestLength, windowEnd - windowStart + 1);
                windowEnd++;
            } else {
                // 현재 문자가 윈도우에 이미 있음: 중복 문자 제거될 때까지 윈도우 축소
                while (s[windowStart] != s[windowEnd]) {
                    uniqueWindowChars.erase(s[windowStart]);
                    windowStart++;
                }
                // 중복 문자를 찾은 후, windowStart를 그 다음 위치로 이동
                windowStart++;
                windowEnd++; // 현재 문자를 처리했으므로 windowEnd도 이동
            }
        }
        return longestLength;
    }
};

접근 방법 3: std::unordered_map을 활용한 최적화된 슬라이딩 윈도우 (문자 마지막 인덱스 저장)

이 방법은 가장 효율적인 슬라이딩 윈도우 접근 방식으로, std::unordered_map을 사용하여 각 문자가 마지막으로 나타난 인덱스를 저장합니다. 이는 windowStart 포인터의 이동을 더욱 최적화합니다.

• windowEnd 포인터를 문자열을 따라 이동합니다.
• 현재 문자(s[windowEnd])가 맵에 이미 존재하고, 해당 문자의 마지막 인덱스(lastSeenCharIndex[s[windowEnd]])가 현재 windowStart보다 크거나 같다면, 이는 현재 윈도우 내에 중복 문자가 존재한다는 의미입니다.
• 이 경우, windowStart 포인터는 중복 문자의 이전 출현 위치 바로 다음 인덱스(lastSeenCharIndex[s[windowEnd]] + 1)로 이동해야 합니다. windowStart는 항상 앞으로만 이동해야 하므로, windowStart = std::max(windowStart, lastSeenCharIndex[s[windowEnd]] + 1)을 사용하여 포인터가 역행하지 않도록 합니다.
• 맵에는 항상 현재 문자의 최신 인덱스를 lastSeenCharIndex[s[windowEnd]] = windowEnd로 업데이트합니다.
• 현재 윈도우 길이(windowEnd - windowStart + 1)를 계산하고 maxUniqueLength를 업데이트합니다.

#include <string>
#include <unordered_map>
#include <algorithm> // std::max를 위해

class Solution {
public:
    int getLongestUniqueSubstringLength(const std::string& str) {
        int windowStart = 0;
        int maxUniqueLength = 0;
        // 문자와 해당 문자가 마지막으로 나타난 인덱스를 저장
        std::unordered_map<char, int> lastSeenCharIndex; 

        for (int windowEnd = 0; windowEnd < str.length(); ++windowEnd) {
            char currentChar = str[windowEnd];

            // 현재 문자가 맵에 존재하고, 그 마지막 인덱스가 현재 윈도우 시작보다 크거나 같으면
            if (lastSeenCharIndex.count(currentChar) && lastSeenCharIndex[currentChar] >= windowStart) {
                // 윈도우 시작 포인터를 중복 문자의 이전 출현 위치 바로 다음으로 이동
                // 이전에 windowStart가 더 큰 값으로 이동했다면, 그 값을 유지
                windowStart = std::max(windowStart, lastSeenCharIndex[currentChar] + 1);
            }
            
            // 현재 문자의 최신 인덱스를 맵에 업데이트
            lastSeenCharIndex[currentChar] = windowEnd;
            
            // 현재 윈도우의 길이 계산 및 최대 길이 업데이트
            maxUniqueLength = std::max(maxUniqueLength, windowEnd - windowStart + 1);
        }
        return maxUniqueLength;
    }
};