পাইথনে সাবস্ট্রিং থেকে প্যালিনড্রোম তৈরি করা সম্ভব কিনা যাচাই

মনে করুন আমাদের একটি স্ট্রিং s আছে, আমাদের s-এর সাবস্ট্রিং-গুলোর ওপর কোয়েরি করতে হবে। প্রতিটি কোয়েরি queries[i]-তে তিনটি অংশ থাকে [left, right, k]। আমরা সাবস্ট্রিং s[left] থেকে s[right] রি-অ্যারেঞ্জ করতে পারি, এবং তারপর সেগুলোর মধ্যে সর্বোচ্চ k টি ক্যারেক্টার যেকোনো লোয়ারকেস ইংরেজি অক্ষরে রিপ্লেস করতে পারি। যদি উপরের অপারেশনগুলো করার পর সাবস্ট্রিংটি প্যালিনড্রোম হতে পারে, তবে কোয়েরির ফলাফল true, অন্যথায় false। আমাদের একটি answer[] অ্যারে বের করতে হবে, যেখানে answer[i] হলো i-তম কোয়েরি queries[i]-র ফলাফল।

উদাহরণস্বরূপ, ইনপুট যদি "abcda" হয়, এবং কোয়েরি হয় [[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 ১ করে বাড়ান, one := 0।
  • for i in range 0 to 25
    • one := one + (dp[r, i] - dp[l - 1, i]) mod 2
  • true রিটার্ন করুন, যখন one // 2 <= k, অন্যথায় false।
• makeDP() নামক আরেকটি মেথড ডিফাইন করুন, এটি dp ম্যাট্রিক্স এবং s নেবে। এটি নিচের মতো কাজ করবে:
  • for i in range 0 to length of s
    • for j in range 0 to 25
      • dp[i, j] := dp[i - 1, j]
    • dp[i, ASCII of s[i] - ASCII of 'a'] ১ বাড়ান।
• মেইন মেথড হবে নিচের মতো:
  • n := size of string s, s := " " + s
  • dp := (n + 1) x 26 অর্ডারের একটি ম্যাট্রিক্স, ০ দিয়ে পূরণ
  • makeDP(dp, s) কল করুন।
  • res := q-এর লেঞ্জির সমান সাইজের অ্যারে, false দিয়ে পূরণ
  • for i in range 0 to length of q - 1
    • res[i] := solve(dp, q[i])
  • return res

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

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]