ধরি আমাদের একটি লোয়ারকেস স্ট্রিং s আছে। আমাদের যাচাই করতে হবে s-এ অক্ষরগুলোর ফ্রিকোয়েন্সি যেকোনোভাবে সাজালে কি রিকামান সিকোয়েন্স (প্রথম টার্ম বাদ দিয়ে) তৈরি করে।
রিকামান সিকোয়েন্স নিচের মতো:
a₀ = 0, aₙ = aₙ₋₁ - n (যদি aₙ₋₁ - n > 0 এবং সিকোয়েন্সে না থাকে), অন্যথায় aₙ₋₁ + n
রিকামান সিকোয়েন্সের কিছু আইটেম: [0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, ...] (প্রথম টার্ম 0 বাদ দেওয়া হয়েছে)
উদাহরণস্বরূপ, s = "pppuvuuqquuu" হলে আউটপুট হবে True, কারণ ক্যারেক্টার ও ফ্রিকোয়েন্সি: (p, 3), (u, 6), (v, 1), (q, 2)। ফ্রিকোয়েন্সিগুলো রিকামান সিকোয়েন্সের প্রথম কয়েকটি টার্ম [1, 3, 6, 2] তৈরি করে।
সমাধানের ধাপসমূহ
- freq := s-এ থাকা সব ক্যারেক্টার এবং তাদের ফ্রিকোয়েন্সির ম্যাপ
- n := freq-এর সাইজ
- array := প্রথম n টি রিকামান সিকোয়েন্স টার্ম
- প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি array-তে আছে কিনা চেক করুন
- সব ফ্রিকোয়েন্সি মিললে true, অন্যথায় false রিটার্ন করুন
উদাহরণ
from collections import defaultdict
def recaman(array, n):
array[0] = 0
for i in range(1, n + 1):
temp = array[i - 1] - i
for j in range(i):
if array[j] == temp or temp < 0:
temp = array[i - 1] + i
break
array[i] = temp
def solve(s):
freq = defaultdict(int)
for i in range(len(s)):
freq[s[i]] += 1
n = len(freq)
array = [0] * (n + 1)
recaman(array, n)
f = 1
for keys in freq.keys():
is_found = 0
for j in range(1, n + 1):
if freq[keys] == array[j]:
is_found = 1
break
if not is_found:
f = 0
break
return True if f else False
s = "pppuvuuqquuu"
print(solve(s))
ইনপুট
"pppuvuuqquuu"
আউটপুট
True
