↓ Skip to main content
j2234’s log

1371. Find the Longest Substring Containing Vowels in Even Counts

·158 words·1 min· loading
DEV Leetcode
Table of Contents

문제링크

설명
#

임의의 ASCII 문자열 S가 주어졌을때, 모음 {'a','e','i','o','u'} 를 각각 짝수번 포함(0번도 가능) 하고 있는 부분 문자열 중 가장 긴 길이를 구하여라

"leetcodeisgreat" => "leetc" => 5

💡풀이
#

처음에 투포인터 문제인줄 알아서 많이 헤멨다

  1. 첫 상태를 정의한다 ( 모든 모음이 0번 나타난 상태)
  2. 모음을 2의 제곱 비트로 정의하고, 모음이 나타날때마다 비트마스크를 업데이트한다. 이전에 기록되지 않았다면 map에 넣는다
  3. 비트마스크가 이미 존재한다면, 이전 비트마스크와 현재 비트마스크 사이에는 모든 모음이 짝수번 존재하므로, 최대길이와 비교한다

코드
#

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        
        vowels = {'a': 1<<0, 'e': 1<<1, 'i': 1<<2, 'o': 1<<3, 'u': 1<<4}
        #  vowels = {'a':1, 'e': 2, 'i': 3, 'o': 4, 'u': 5} # 왜 안되는지 모르겠다면, 3인 경우를 생각해보자

        my_map ={ 0 : -1}
        mask = 0
        answer= 0
    
        for i,c in enumerate(s):

            if c in vowels:
                mask ^= vowels[c]

            if mask not in my_map:
                my_map[mask] = i
            else :
                answer = max(answer, i-my_map[mask])

        return answer

😎그다지 어렵진 않지만, 풀이가 재미있는 문제였다.