পাইথনে রিপিটিং লেটার এড়াতে ন্যূনতম ডিলিশন কস্ট বের করার প্রোগ্রাম

মান লিজিয়ে একটি স্ট্রিং আছে s এবং আরেকটি ইন্টিজার অ্যারে cost যেখানে cost[i] হল s-এর i-তম ক্যারেক্টার ডিলিট করার খরচ। আমাদের ন্যূনতম কস্টে ডিলিশন করতে হবে যাতে দুটি একই অক্ষর পাশাপাশি না থাকে। সকল ডিলিশন একসাথে হবে, তাই একটা মুছে দিলে অন্যগুলোর কস্ট পরিবর্তন হবে না।

যেমন, ইনপুট হলে s = "pptpp", cost = [2,3,4,5,2], তবে আউটপুট হবে 4 কারণ প্রথম ও শেষ 'p' মুছে দিলে (খরচ ২+২=৪) স্ট্রিং হবে "ptp" যেখানে কোনো দুটি একই অক্ষর পাশাপাশি নেই।

সমাধানের ধাপসমূহ

cost_f := 0, i := 1, ind := 0
i = 1 থেকে len(s)-1 পর্যন্ত:
- cur, c_cost := s[i], cost[i]
- prev, p_cost := s[i-1], cost[i-1]
- যদি ind == 1 হয়, তবে prev, p_cost := prev_i, cost_i
- যদি cur == prev হয়, তবে:
  - যদি c_cost >= p_cost হয়, তবে cost_f += p_cost, prev_i=cost_i=0, ind=0
  - যদি c_cost < p_cost হয়, তবে cost_f += c_cost, ind=1, prev_i=prev, cost_i=p_cost
- অন্যথায়, prev_i=cost_i=0, ind=0
cost_f রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(s, cost):
    cost_f = 0
    i = 1
    ind = 0
    for i in range(1, len(s)):
        cur, c_cost = s[i], cost[i]
        prev, p_cost = s[i-1], cost[i-1]
        if ind == 1:
            prev, p_cost = prev_i, cost_i
        if cur == prev:
            if c_cost >= p_cost:
                cost_f += p_cost
                prev_i, cost_i = 0, 0
                ind = 0
            if c_cost < p_cost:
                cost_f += c_cost
                ind = 1
                prev_i, cost_i = prev, p_cost
        else:
            prev_i, cost_i = 0, 0
            ind = 0
    return cost_f

s = "pptpp"
cost = [2,3,4,5,2]
print(solve(s, cost))

ইনপুট

"pptpp", [2,3,4,5,2]