মান লাগিয়ে, আমাদের একটি স্ট্রিং s আছে। একটি স্প্লিটকে ভালো স্প্লিট বলা হয় যখন s কে ২টি নন-এম্পটি স্ট্রিং p এবং q-তে স্প্লিট করা যায় যাতে তাদের কনক্যাটিনেশন s-র সমান হয় এবং p এবং q-তে ডিস্টিংচ লেটারের সংখ্যা সমান হয়। আমাদের s-তে কতগুলো ভালো স্প্লিট করা যায় তা বের করতে হবে।
যেমন, ইনপুট s = "xxzxyx" হলে, আউটপুট হবে 2 কারণ অনেকভাবে স্প্লিট করা যায় কিন্তু ("xxz", "xyx") বা ("xxzx", "yx") হলে সেগুলো ভালো।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- result := 0
- left := একটি খালি কাউন্টার ফ্রিকোয়েন্সি গুনতে
- right := s-এ থাকা প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি কাউন্ট
- s-এ থাকা প্রতিটি c জন্য:
- left[c] := left[c] + 1
- right[c] := right[c] - 1
- যদি right[c] শূন্য হয়, তবে right[c] ডিলিট করুন
- যদি left এবং right-এর আকার সমান হয়, তবে result := result + 1
- result রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
from collections import Counter
def solve(s):
result = 0
left, right = Counter(), Counter(s)
for c in s:
left[c] += 1
right[c] -= 1
if not right[c]:
del right[c]
if len(left) == len(right):
result += 1
return result
s = "xxzxyx"
print(solve(s))
ইনপুট
"xxzxyx"
আউটপুট
2
