मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं, और दो मान p और q हैं। हमें यह जांचना है कि क्या s से t प्राप्त करना संभव है जैसे कि s को p संख्या के वर्णों के समूहों में विभाजित किया गया है सिवाय अंतिम समूह के जिसमें वर्ण ≤ p होंगे और हम प्रत्येक समूह से अधिकतम q संख्या में वर्ण चुन सकते हैं, और t में वर्णों का क्रम s के समान होना चाहिए।
तो, यदि इनपुट s = "mnonnopeqrst", t = "moprst", p = 5, q = 2 है, तो आउटपुट True होगा क्योंकि हम "mnonn", "opeqr", "st" जैसे विभाजन बना सकते हैं, अब "mnonn" और "opeqr" से 2 वर्ण उपस्ट्रिंग "mo" और "pr" लेकर फिर "st" पहले से ही है इसलिए इन दो लंबाई उपस्ट्रिंग का उपयोग करके हम सरल संयोजन द्वारा t उत्पन्न कर सकते हैं।
हल करने के चरण
- temp := सभी कुंजियों के लिए खाली सूची वाला खाली मैप
- l := s की लंबाई के समान आकार की सूची और 0 से भरें
- रेंज 0 से s के आकार तक के लिए i, करें:
- i को temp['a'] के अंत में डालें
- low := 0
- रेंज 0 से t के आकार - 1 तक के लिए i, करें:
- indices := temp['a']
- it := indices सूची में low को डालने का सूचकांक क्रम बनाए रखने के लिए
- यदि it, indices के आकार - 1 के समान है, तो:
- False लौटाएं
- count := (indices[it] / p) का भागफल
- l[count] := l[count] + 1
- यदि l[count] >= q, तो:
- count := count + 1
- low := count * p
- अन्यथा,
- low := indices[it] + 1
- True लौटाएं
उदाहरण
from bisect import bisect_left
from collections import defaultdict
def solve(s, t, b, m):
temp = defaultdict(list)
l = [0] * len(s)
for i in range(len(s)):
temp['a'].append(i)
low = 0
for i in range(len(t)):
indices = temp['a']
it = bisect_left(indices, low)
if it == len(indices):
return False
count = indices[it] // b
l[count] = l[count] + 1
if l[count] >= m:
count += 1
low = count * b
else:
low = indices[it] + 1
return True
s = "mnonnopeqrst"
t = "moprst"
p = 5
q = 2
print(solve(s, t, p, q))
इनपुट
"mnonnopeqrst", "moprst", 5, 2
आउटपुट
True
