C++-এ স্ট্রিং-এর সর্বোচ্চ ওজনραν্তরূপান্তর (Maximum Weight Transformation of a String)

সমস্যা বিবরণ

শুধু 'A' এবং 'B' ধারণকারী একটি স্ট্রিং দেওয়া আছে। স্ট্রিং-এর যেকোনো ক্যারেক্টার টগল (A→B বা B→A) করে নতুন স্ট্রিং তৈরি করা যায়। সবচেয়ে বেশি ওজন (weight) বিশিষ্ট রূপান্তর খুঁজে বের করতে হবে।

ওজন গণনার ফর্মুলা

Weight = (পেয়ার সংখ্যা × ৪) + (একক ক্যারেক্টার সংখ্যা × ১) - (টগল সংখ্যা)

দুটি পরপর ভিন্ন ক্যারেক্টারকে একটি পেয়ার মনে করা হয়
একটি পেয়ার ওজন = ৪
একক ক্যারেক্টার ওজন = ১

উদাহরণ

ইনপুট: "AA" → আউটপুট: ৩

সম্ভাব্য রূপান্তর: "AA", "AB", "BA", "BB"
সর্বোচ্চ ওজন: "AB" বা "BA" → এক পেয়ার (৪) - এক টগল (১) = ৩

এলগরিদম (ডাইনামিক প্রোগ্রামিং)

1. যদি n == 1: maxWeight = 1
2. যদি str[0] != str[1]:
      maxWeight = max(1 + maxWeight(str[1..n-1]), 4 + maxWeight(str[2..n-1]))
3. অন্যথায়:
      maxWeight = max(1 + maxWeight(str[1..n-1]), 3 + maxWeight(str[2..n-1]))

C++ প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int getMaxRec(string &str, int i, int n, int lookup[]) {
    if (i >= n) return 0;
    if (lookup[i] != -1) return lookup[i];
    
    int ans = 1 + getMaxRec(str, i + 1, n, lookup);
    if (i + 1 < n) {
        if (str[i] != str[i+1])
            ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans);
        else
            ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans);
    }
    return lookup[i] = ans;
}

int getMaxWeight(string str) {
    int n = str.length();
    int lookup[n];
    memset(lookup, -1, sizeof lookup);
    return getMaxRec(str, 0, str.length(), lookup);
}

int main() {
    string str = "AA";
    cout << "Result = " << getMaxWeight(str) << endl;
    return 0;
}

আউটপুট

Result = 3