পাইথনে সাবস্ট্রিং রিমুভ করে সর্বোচ্চ স্কোর গণনা করার প্রোগ্রাম

মনে করুন একটি স্ট্রিং s এবং দুটি মান x এবং y আছে। আমরা নিচের দুটি অপারেশন যেকোনো সংখ্যক বার করতে পারি।

"ab" সাবস্ট্রিং খুঁজুন, থাকলে এটি রিমুভ করে x পয়েন্ট পান।
"ba" সাবস্ট্রিং খুঁজুন, থাকলে এটি রিমুভ করে y পয়েন্ট পান।

s-এর ওপর এই অপারেশনগুলো প্রয়োগ করে সর্বোচ্চ পয়েন্ট বের করতে হবে।

যেমন, ইনপুট s = "cbbaacdeabb", x = 4, y = 5 হলে, আউটপুট হবে ১৪ কারণ:

শুরুতে স্ট্রিং "cbbaacdeabb", "ab" রিমুভ করলে ৪ পয়েন্ট, স্ট্রিং হয়ে যায় "cbbaacdeb"
"ba" রিমুভ করলে আরও ৫ পয়েন্ট, মোট ৯, স্ট্রিং "cbacdeb"
আবার "ba" রিমুভ করলে ৫ পয়েন্ট, মোট ১৪, স্ট্রিং "ccdeb"
এখন আর কিছু রিমুভ করা যায় না

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

a := 'a', b := 'b'
ans := 0, a_st := 0, b_st := 0
যদি y > x হয়, তবে
- a এবং b স্ব্যাপ করুন
- x এবং y স্ব্যাপ করুন
s-এ থাকা প্রতিটি c-এর জন্য
- যদি c == a হয়, তবে
  - a_st := a_st + 1
- অন্যথায় যদি c == b হয়, তবে
  - যদি a_st > 0 হয়, তবে
    - ans := ans + x
    - a_st := a_st - 1
  - অন্যথায়,
    - b_st += 1
- অন্যথায়,
  - ans := ans + y * min(a_st, b_st)
  - a_st := 0, b_st := 0
return ans + y * min(a_st, b_st)

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

 def solve(s, x, y):    a = 'a'    b = 'b'    ans = 0    a_st = 0    b_st = 0    if y > x:       a,b = b,a       x,y = y,x    for c in s:       if c == a:          a_st += 1       elif c == b:          if a_st:             ans += x             a_st -= 1          else: b_st += 1       else:          ans += y * min(a_st, b_st)          a_st = 0          b_st = 0    return ans + y * min(a_st, b_st) s = "cbbaacdeabb" x = 4 y = 5 print(solve(s, x, y))

ইনপুট

"cbbaacdeabb", 4, 5