[코드트리 챌린지] 7주차 Two Pointer - Two Pointer / 중복되지 않는 가장 긴 문자열

 

https://www.codetree.ai/missions/8/problems/longest-not-duplicated-substring/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

string s;
int visited[30]; // 각 문자의 등장 횟수를 저장함

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    int n = s.length();

    int j = -1; 
    int len = 0; // 중복되지않는 문자열의 길이
    int maxLen = INT_MIN; // 중복되지않는 문자열의 길이 중 최대길이

    for (int i = 0; i < n; i++) {
        
        // j + 1이 s의 길이 내에 존재하거나
        // 그 문자열이 중복되지 않는다면 len과 j를 증가시킴
        // visited[s[j+1] - 'a']는 j+1 위치 문자의 방문 횟수를 의미함
        while (j + 1 < n && visited[s[j + 1] - 'a'] < 1) {
            visited[s[j + 1] - 'a']++;
            len++;
            j++;
        }

        // 중복없는 최대 문자열 길이를 갱신
        maxLen = max(maxLen, len);

        // i가 증가하므로 그 위치의 문자 방문 횟수와 길이를 감소시킴
        len--;
        visited[s[i] - 'a']--;
    }

    cout << maxLen;

}

문자열 s를 입력받아 n을 s의 길이로 초기화 시킵니다.

len은 중복되지 않는 문자열의 길이를 의미하며 maxLen은 그 중 최대길이를 의미합니다.

for문을 통해 i를 0~n-1까지 시작점으로 둔 뒤 j를 while문에 따라 증가시켜 길이를 구하도록합니다.

j+1 < n인 경우 즉, s의 길이보다 작거나 visited[s[j+1] - 'a'] 가 1보다 작은 경우 즉,
그 이전에 등장한 적이 없다면 등장횟수를 증가시키고 len과 j를 1씩 증가시킵니다.

중복되거나 길이를 넘어서게 된다면 이때 maxLen을 갱신해주고 i를 1 증가시키므로 len과 등장 횟수를
1 감소시킵니다.

위 문제에서 핵심적 역할을 하는 것은 visited 배열입니다. -'a'를 해줌으로써 문자를 index로 활용
할 수 있게 해주었습니다.