पायथन में उस सबसीक्वेंस की लंबाई ज्ञात करने का प्रोग्राम जिसे हटाने के बाद भी t, s का सबसीक्वेंस रहे

मान लीजिए हमारे पास एक स्ट्रिंग s और दूसरी स्ट्रिंग t है। और t, s का सबसीक्वेंस है। हमें उस सबस्ट्रिंग की अधिकतम लंबाई ज्ञात करनी है जिसे हम s से हटा सकते हैं ताकि t अभी भी s का सबसीक्वेंस रहे।

उदाहरण के लिए, s = "xyzxyxz", t = "yz" के लिए आउटपुट 4 होगा।

एल्गोरिदम

left := [], right := []
बाएं से दाएं स्कैन करके t के वर्णों के s में सबसे पहले मिलने वाले सूचकांक left में संग्रहीत करें
दाएं से बाएं स्कैन करके t के वर्णों के s में सबसे अंत में मिलने वाले सूचकांक right में संग्रहीत करें
c1 := s के अंत से पहला मिलान के बाद के शेष वर्ण
c2 := s के शुरू से अंतिम मिलान से पहले के वर्ण
c3 := max(right[i+1] - left[i] - 1) for i in 0..len(t)-2
max(c1, c2, c3) वापस करें

उदाहरण

class Solution:
    def solve(self, s, t):
        left = []
        right = []
        c1 = c2 = c3 = -1
        j = 0
        for i in range(len(s)):
            if s[i] == t[j]:
                left.append(i)
                j += 1
            if j == len(t):
                c1 = len(s) - i - 1
                break
        j = len(t) - 1
        for i in range(len(s)-1, -1, -1):
            if s[i] == t[j]:
                right.insert(0, i)
                j -= 1
            if j == -1:
                c2 = i
                break
        for i in range(len(t)-1):
            c3 = max(c3, right[i+1] - left[i] - 1)
        return max(c1, c2, c3)

ob = Solution()
s = "xyzxyxz"
t = "yz"
print(ob.solve(s, t))

इनपुट

"xyzxyxz", "yz"