ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের s-এর সাবস্ট্রিংগুলিতে প্রশ্ন করতে হবে। প্রতিটি ক্যোয়ারী কোয়েরির জন্য [i], তিনটি অংশ আছে [বাম, ডান, কে], আমরা সাবস্ট্রিং s[বাম], ..., s[ডান] পুনর্বিন্যাস করতে পারি, এবং তারপর প্রতিস্থাপন করতে তাদের মধ্যে k পর্যন্ত বেছে নিতে পারি যেকোনো ছোট হাতের ইংরেজি অক্ষর। উপরে উল্লিখিত ক্রিয়াকলাপগুলির পরে যদি সাবস্ট্রিংটি প্যালিনড্রোম হওয়া সম্ভব হয় তবে প্রশ্নের ফলাফলটি সত্য। অন্যথায় মিথ্যা। আমাদের একটি অ্যারে উত্তর খুঁজতে হবে[], যেখানে উত্তর[i] হল i-th ক্যোয়ারী কোয়েরির ফলাফল[i]।
উদাহরণস্বরূপ, যদি ইনপুটটি "abcda" হয়, প্রশ্নগুলি [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0, 4,1]], তাহলে আউটপুট হবে [সত্য, মিথ্যা, মিথ্যা, সত্য, সত্য]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- সলভ নামক একটি পদ্ধতির সংজ্ঞা দিন, এটি dp ম্যাট্রিক্স এবং q নেবে। এটি নিচের মত কাজ করবে -
- l :=q[0], r :=q[1], k :=q[2], তারপর l এবং r 1 দ্বারা বাড়ান, one :=0
- আমি 0 থেকে 25 রেঞ্জের জন্য
- এক :=এক + (dp[r, i] – dp[l – 1, i]) মোড 2
- সত্য প্রত্যাবর্তন করুন, যখন এক / 2 <=k এর পূর্ণসংখ্যা ভাগ, অন্যথায় মিথ্যা
- makeDP() নামক আরেকটি পদ্ধতির সংজ্ঞা দিন, এটি dp ম্যাট্রিক্স এবং s নেবে, এটি নীচের মত কাজ করবে -
- আমি 0 থেকে s
- এর দৈর্ঘ্যের মধ্যে 0 থেকে 25 রেঞ্জের মধ্যে j-এর জন্য
- dp[i, j] :=dp[i – 1, j]
- dp[i, s[i]-এর ASCII - 'a'] এর ASCII 1 দ্বারা বাড়ান
- এর দৈর্ঘ্যের মধ্যে
- res[i] :=সমাধান(dp, q[i])
উদাহরণ(পাইথন)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
class Solution(object):
def solve(self,dp,q):
l = q[0]
r = q[1]
k = q[2]
r+=1
l+=1
#arr = [ 0 for i in range(26)]
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]
