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

1371. Find the Longest Substring Containing Vowels in Even Counts

📌 문제 개념

• 주어진 문자열 s에서 모든 모음(a, e, i, o, u)이 짝수 번 등장하는 가장 긴 연속된 부분 문자열의 길이를 찾아야 한다.
• 문제 자체는 굉장히 간단하지만.. 비트마스킹을 많이 풀지 않아보아서 해결하는 아이디어를 떠올리기는 쪼금 어려웠다.

제약 사항
1 <= s.length <= 5 x 10^5

---

📌 접근 방식

1. Brute Force

• s.length가 굉장히 크므로, 모든 substring을 확인하는 방법은 불가능.

2. 비트 마스킹

• 핵심은 비트 마스킹을 사용해서 O(N)으로 해결하는 것이다.
• 우선 비트마스크를 사용하여 모음의 등장 횟수를 관리할 수 있다.
  • 각 모음을 특정 비트 위치에 매핑해서 등장할 때마다 XOR 연산을 수행
  • 이렇게 하면 현재까지의 모음 등장 상태를 5비트로 표현할 수 있다.
• 계속 누적되는 비트마스크 값을 트래킹하면서, 이전에 존재한 값이라면 이 사이의 문자열은 모음이 짝수 개임이 보장이 된다.
  • 두 값이 같다는 것은 이 사이에는 추가적인 모음이 없거나, 모음이 짝수 개 등장했다는 뜻이기도 하다.

---

📌 풀이 설명

1. 모음을 비트 위치에 매핑

모음	비트 위치 (0-based)	비트 값 (1 << index)
a	0	00001 (1)
e	1	00010 (2)
i	2	00100 (4)
o	3	01000 (8)
u	4	10000 (16)

• a, e, i, o, u를 5개의 비트(0~4번 비트)에 매핑한다.
• 문자열을 순회하면서 해당 모음이 등장할 때마다 XOR 연산을 수행하여 비트마스크 값을 업데이트한다.

2. XOR 연산을 이용한 등장 횟수 표현

• 각 모음이 등장할 때마다 해당 비트를 XOR 연산을 통해 토글 시킨다.

• XOR의 특징 - 같은 값을 두 번 XOR 하면 원래 값으로 돌아감

  1010 ^ 1010 = 0000

3. 비트마스크 값이 이전에 등장했는지 확인

• 현재까지의 비트마스킹 상태를 계속 트래킹 하면서 이전에 등장한 값인지 확인한다.
• 만약 있다면, 그 사이의 문자열은 짝수 번의 모음이 존재하기에 가장 긴 길이로 업데이트를 해준다.
• 만약 없다면, 해당 비트마스크 값의 위치를 현 위치로 초기화 해준다.
  • 가장 긴 길이를 구해야 하기에 이 값은 바뀌지 않는다.

---

📌 정답

class Solution {
public:
    int getIndex(char c){
        if(c == 'a'){
            return 0;
        }
        else if(c == 'e'){
            return 1;
        }
        else if(c == 'i'){
            return 2;
        }
        else if(c == 'o'){
            return 3;
        }
        else if(c == 'u') {
            return 4;
        } 

        return -1;
    }

    int findTheLongestSubstring(string s) {
        int arr[33];

        for(int i = 0 ; i<33; i++){
            arr[i] = -2;
        }

        int mask = 0;
        int answer = 0;
        arr[0] = -1;
        for(int i = 0 ; i<s.length(); i++){
            int index = getIndex(s[i]);

            if(index != -1){
                mask ^= (int)pow(2, index);
            }

            if(arr[mask] != -2){
                answer = max(answer, i - arr[mask]);
            } else {
                arr[mask] = i;
            }
        }

        return answer;
    }
};