पायथन में सम स्वर गणना वाले सबसे लंबे सबस्ट्रिंग की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक स्ट्रिंग s (लोअरकेस) है, हमें उस सबसे लंबे सबस्ट्रिंग की लंबाई ढूंढनी है जहां प्रत्येक स्वर (vowel) सम संख्या में आता हो।

उदाहरण के लिए, यदि इनपुट s = "anewcoffeepot" है, तो आउटपुट 10 होगा, क्योंकि सबस्ट्रिंग "wcoffeepot" में दो स्वर 'o' और 'e' हैं, और दोनों दो-दो बार आते हैं।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम बिटमास्क और प्रीफिक्स मैप का उपयोग करेंगे:

• vowels := एक मैप जो स्वरों को संख्यात्मक मान देता है: {a:0, e:1, i:2, o:3, u:4}
• prefix := एक खाली मैप जिसमें (0, -1) की-वैल्यू पेयर डालें
• mask := 0, n := s का आकार, res := 0
• i को 0 से n-1 तक लूप चलाएं:
  • यदि s[i] स्वर है, तो mask := mask XOR (2^vowels[s[i]])
  • यदि mask prefix में नहीं है, तो prefix[mask] := i
  • अन्यथा, res := max(res, i - prefix[mask])
• res लौटाएं

पायथन कार्यान्वयन

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