[LeetCode] 1371. Find the Longest Substring Containing Vowels in Even Counts

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/description/?envType=daily-question&envId=2024-09-15

leetcode - Fine the Longest Substring Containing Vowels in Even Counts

문제 유형 : 비트마스크, 비트 연산, 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.

 

문자열 s가 주어진다. 모음이 짝수번 등장하는 가장 긴 부분문자열의 길이를 구하시오.

 

풀이

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/?envType=daily-question&envId=2024-09-15

의 풀이를 참조했다.

 

길이가 32인 pos배열로 상태를 관리한다. (모음이 5개이므로, 2^5 = 32개의 상태.)

여기에는 각 상태가 최초로 등장한 인덱스를 저장한다. 기저 사례로, pos[0] = 0이다. 모든 알파벳이 없는 상태는 0이니까.

정수 mask로 현재 상태를 저장한다.

 

문자열을 매번 읽으면서, mask에 모음 상태를 업데이트한다.

(a: 0번lsb, e: 1번lsb, i: 2번lsb, o: 3번lsb, u: 4번lsb(msb))

만약 기존에 같은 상태가 존재한다면, 같은 상태의 첫 인덱스와 현재 인덱스의 차 + 1과 가장 긴 부분문자열의 길이를 비교하여 더 긴쪽으로 업데이트한다.

그렇지 않고 최초로 나온 상태라면, 인덱스를 저장한다.

 

최종적으로 가장 긴 부분문자열의 길이를 반환한다.

 

코드

C++

class Solution {
public:
    int findTheLongestSubstring(string s) {
        int n = s.size();
        int mask = 0, maxLength = 0;
        vector<int> pos(32, -1);
        pos[0] = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'a') mask ^= (1 << 0);
            if (s[i] == 'e') mask ^= (1 << 1);
            if (s[i] == 'i') mask ^= (1 << 2);
            if (s[i] == 'o') mask ^= (1 << 3);
            if (s[i] == 'u') mask ^= (1 << 4);
            if (pos[mask] != -1) {
                maxLength = max(maxLength, i + 1 - pos[mask]);
            } else {
                pos[mask] = i + 1;
            }
        }
        return maxLength;
    }
};