पायथन में सबस्ट्रिंग से पालिंड्रोम बना सकते हैं

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें s के सबस्ट्रिंग्स पर क्वेरीज़ करनी हैं। प्रत्येक क्वेरी queries[i] के लिए, तीन भाग हैं [left, right, k], हम सबस्ट्रिंग s[left], ..., s[right] को पुनर्व्यवस्थित कर सकते हैं, और फिर उनमें से k तक को किसी भी लोअरकेस अंग्रेजी अक्षर से बदल सकते हैं। यदि उपरोक्त ऑपरेशन्स के बाद सबस्ट्रिंग पालिंड्रोम बनना संभव है, तो क्वेरी का परिणाम true है। अन्यथा false। हमें एक ऐरे answer[] ढूंढना है, जहां answer[i] i-वें क्वेरी queries[i] का परिणाम है।

उदाहरण के लिए, यदि इनपुट \"abcda\" है, queries [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]] जैसा है, तो आउटपुट [true, false, false, true, true] होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• solve नामक एक मेथड परिभाषित करें, यह dp मैट्रिक्स और q लेगा। यह नीचे की तरह काम करेगा -
• l := q[0], r := q[1], k := q[2], फिर l और r को 1 से बढ़ाएं, one := 0
• i को 0 से 25 तक रेंज में
  • one := one + (dp[r, i] - dp[l - 1, i]) mod 2
• true लौटाएं, जब one / 2 का पूर्णांक विभाजन <= k, अन्यथा false
• makeDP() नामक एक और मेथड परिभाषित करें, यह dp मैट्रिक्स और s लेगा, यह नीचे की तरह काम करेगा -
• i को 0 से s की लंबाई तक रेंज में
  • j को 0 से 25 तक रेंज में
    • dp[i, j] := dp[i - 1, j]
  • dp[i, s[i] का ASCII - 'a' का ASCII] को 1 से बढ़ाएं
• मुख्य मेथड इस तरह होगा -
• n := स्ट्रिंग s का आकार, s := \" \" कन्कैटिनेट s
• dp := (n + 1) x 26 ऑर्डर का एक मैट्रिक्स, और इसे 0 से भरें
• makeDP(dp, s) कॉल करें
• res := q की लंबाई के समान आकार का एक ऐरे, और इसे false से भरें
• i को 0 से q की लंबाई - 1 तक रेंज में
  • res[i] := solve(dp, q[i])
• res लौटाएं

उदाहरण (पायथन)

बेहतर समझ पाने के लिए निम्न कार्यान्वयन देखें -

class Solution(object):
    def solve(self,dp,q):
        l = q[0]
        r = q[1]
        k = q[2]
        r+=1
        l+=1
        one = 0
        for i in range(26):
            one += (dp[r][i]-dp[l-1][i])%2
        return one//2<=k
    def make_dp(self,dp,s):
        for i in range(1,len(s)):
            for j in range(26):
                dp[i][j] = dp[i-1][j]
            dp[i][ord(s[i])-ord('a')]+=1
    def canMakePaliQueries(self, s, q):
        n = len(s)
        s = \" \"+s
        dp = [[0 for i in range(26)] for j in range(n+1)]
        self.make_dp(dp,s)
        res = [False for i in range(len(q))]
        for i in range(len(q)):
            res[i] = self.solve(dp,q[i])
        return res

ob = Solution()
print(ob.canMakePaliQueries(\"abcda\", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))

इनपुट

\"abcda\" [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]

आउटपुट

[True, False, False, True, True]