문제 개요
문자열 s가 주어졌을 때, 다섯 개의 모음인 'a', 'e', 'i', 'o', 'u'가 모두 짝수 번씩 등장하는 가장 긴 부분 문자열(substring)의 길이를 구해야 합니다. 예를 들어 문자열이 "helloworld"라면, 조건을 만족하는 가장 긴 부분 문자열의 길이는 8입니다.
풀이 접근 방식
이 문제의 핵심 아이디어는 모음별 홀짝 상태를 하나의 키로 압축하는 것입니다. 문자열을 왼쪽부터 순회하면서 각 시점마다 지금까지 등장한 모음의 개수를 세고, 각 모음이 홀수 번인지 짝수 번인지를 5자리 상태 문자열(예: "01001")로 표현합니다.
같은 상태 문자열이 두 번 나타났다면, 그 두 지점 사이 구간에서는 어떤 모음도 홀짝성이 바뀌지 않았다는 의미입니다. 즉, 해당 구간 내에서는 모든 모음이 짝수 번 등장했으므로 유효한 후보가 됩니다. 따라서 각 상태가 처음 등장한 인덱스를 맵에 저장해 두었다가, 동일한 상태가 다시 나타날 때 두 인덱스의 차이로 최대 길이를 갱신하면 됩니다.
알고리즘 단계
ret := 0으로 초기화하고, 두 개의 맵 m과 cnt를 준비한 뒤 m["00000"] := -1로 설정합니다.
vowels 배열에 'a', 'e', 'i', 'o', 'u'를 저장합니다.
i를 0부터 s.size() - 1까지 반복합니다.
x := s[i]로 설정하고 cnt[x]를 1 증가시킨 뒤, temp := 빈 문자열로 초기화합니다.
k를 0부터 4까지 순회하며 temp := temp + ('0' + cnt[vowels[k]] mod 2)로 현재까지의 홀짝 상태 문자열을 만듭니다.
m에 temp가 이미 존재하면 ret := max(ret, i - m[temp])로 갱신하고, 존재하지 않으면 m[temp] := i로 저장합니다.
반복이 끝나면 ret을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findTheLongestSubstring(string s) {
int ret = 0;
map <string, int> m;
map <char, int> cnt;
m["00000"] = -1;
char vowels[5] = {'a', 'e', 'i', 'o', 'u'};
for(int i = 0; i < s.size(); i++){
char x = s[i];
cnt[x]++;
string temp = "";
for(int k = 0; k < 5; k++){
temp+= ('0' + (cnt[vowels[k]] % 2));
}
if(m.count(temp)){
ret = max(ret, i - m[temp]);
}
else{
m[temp] = i;
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findTheLongestSubstring("helloworld"));
}실행 결과
입력
"helloworld"
출력
8
복잡도 분석
위 알고리즘은 문자열 전체를 한 번만 순회하므로 시간 복잡도는 O(n × 5), 즉 O(n)입니다. 또한 상태 문자열의 종류가 제한적이므로 추가 메모리 사용량 역시 O(n) 수준으로 매우 효율적입니다. 이처럼 홀짝 상태를 키로 관리하는 기법은 누적 카운트 기반의 부분 배열·부분 문자열 문제에서 널리 활용되는 강력한 패턴입니다.