Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 모음 개수가 짝수인 가장 긴 부분 문자열의 길이를 찾는 프로그램


문자열 s(소문자)가 있다고 가정하면 각 모음이 짝수번 나타나는 가장 긴 부분 문자열의 길이를 찾아야 합니다.

따라서 입력이 s ="anewcoffeepot"과 같으면 하위 문자열 "wcoffeepot"에 두 개의 모음 "o"와 "e"가 있고 둘 다 두 번 발생하므로 출력은 10이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 모음 :=모음과 숫자 값을 {a:0, e:1, i:2, o:3, u:4}로 지정하는 맵

  • 접두사 :=빈 맵이고 여기에 키-값 쌍(0, -1)을 삽입합니다.

  • 마스크 :=0, n :=s의 크기, 해상도 :=0

  • 0에서 n 사이의 i에 대해 수행

    • s[i]가 모음이면

      • 마스크 :=마스크 XOR (2^모음[s[i]])

    • 마스크가 접두어에 없으면

      • 접두사[마스크] :=i

    • 그렇지 않으면

      • res :=최대 res 및 (i - 접두사[마스크])

  • 반환 해상도

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:
   def solve(self, s):
      vowels = {"a": 0, "e": 1, "i": 2, "o": 3, "u": 4}
      prefix = {0: −1}
      mask = 0
      n = len(s)
      res = 0
      for i in range(n):
         if s[i] in vowels:
            mask ^= 1 << vowels[s[i]]
         if mask not in prefix:
            prefix[mask] = i
         else:
            res = max(res, i − prefix[mask])
      return res
ob = Solution()
s = "anewcoffeepot"
print(ob.solve(s))

입력

"anewcoffeepot"

출력

10