मान लीजिए हमारे पास दो गैर-खाली स्ट्रिंग्स s और t हैं जो समान लंबाई के हैं। हमें उन्हें सबस्ट्रिंग्स में विभाजित करना है ताकि s और t के प्रत्येक जोड़े का सबस्ट्रिंग समान आकार का हो और वे एक-दूसरे के एनाग्राम हों। अब उन कट इंडेक्स को ढूंढें जिनके परिणामस्वरूप s और t के अधिकतम कट हों। यदि कोई परिणाम नहीं मिलता है, तो खाली सूची वापस करें।
उदाहरण के लिए, यदि इनपुट है s = "bowcattiger" t = "owbactietgr", तो आउटपुट होगा [0, 3, 5, 6, 10], क्योंकि हम स्ट्रिंग को 5 पार्टीशन में विभाजित कर सकते हैं ताकि प्रत्येक स्ट्रिंग एक-दूसरे की एनाग्राम हो। s = ["bow", "ca", "t", "tige", "r"], t = ["owb", "ac", "t", "ietg", "r"]
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- intervals := एक नई सूची
- cs := s में मौजूद वर्ण और उसकी आवृत्ति के साथ एक मैप
- ct := t में मौजूद वर्ण और उसकी आवृत्ति के साथ एक मैप
- यदि cs, ct के समान नहीं है, तो
- एक नई सूची वापस करें
- x के लिए s के आकार - 1 से 0 तक नीचे की ओर, करें
- cs[s[x]] := cs[s[x]] - 1
- ct[t[x]] := ct[t[x]] - 1
- यदि cs, ct के समान है, तो
- x को intervals के अंत में डालें
- intervals सूची को सॉर्ट करें और वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
from collections import Counter class Solution: def solve(self, a, b): intervals = [] ca = Counter(a) cb = Counter(b) if ca != cb: return [] for x in reversed(range(len(a))): ca[a[x]] -= 1 cb[b[x]] -= 1 if ca == cb: intervals.append(x) return sorted(intervals) ob = Solution() s = "bowcattiger" t = "owbactietgr" print(ob.solve(s, t))
इनपुट
"bowcattiger", "owbactietgr"
आउटपुट
[0, 3, 5, 6, 10]
