সি++-এ স্ট্রিংকে ন্যূনতম প্যালিনড্রোমে ভাগ করে প্যালিনড্রোম সংখ্যা গণনার প্রোগ্রাম

সমস্যা বিবরণ

একটি লোয়ারকেস স্ট্রিং s দেওয়া আছে। এটিকে যতসামান্য কম সংখ্যক সাবস্ট্রিংয়ে ভাগ করতে হবে যাতে প্রতিটি সাবস্ট্রিং একটি প্যালিনড্রোম হয়। তারপর সেই প্যালিনড্রোমগুলোর সংখ্যা বের করতে হবে।

উদাহরণস্বরূপ, s = "levelracecar" হলে আউটপুট হবে 2, কারণ এটি "level" এবং "racecar" — দুটি প্যালিনড্রোমে ভাগ করা যায়।

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

1. n := s-এর আকার।
2. result[n+1] অ্যারে তৈরি করুন।
3. result[n] = -1 সেট করুন।
4. i = n-1 থেকে 0 পর্যন্ত লুপ চালান।
5. প্রতিটি i এর জন্য result[i] = n - i - 1 (সর্বোচ্চ কাটা) ইনিশিয়ালাইজ করুন।
6. j = i থেকে n-1 পর্যন্ত লুপ চালিয়ে চেক করুন s[i...j] প্যালিনড্রোম কিনা।
7. যদি হয়, তবে result[i] = min(result[i], 1 + result[j+1])।
8. শেষে result[0] + 1 রিটার্ন করুন।

উদাহরণ কোড

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

class Solution {
public:
    bool isPalindrome(string A) {
        int left = 0, right = A.size() - 1;
        while (left < right) {
            if (A[left] != A[right]) return false;
            left++; right--;
        }
        return true;
    }

    int solve(string A) {
        int n = A.size();
        vector<int> result(n + 1);
        result[n] = -1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = n - i - 1;
            for (int j = i; j < n; j++) {
                if (isPalindrome(A.substr(i, j - i + 1)))
                    result[i] = min(result[i], 1 + result[j + 1]);
            }
        }
        return result[0] + 1;
    }
};

int main() {
    string s = "levelracecar";
    cout << solve(s);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: "levelracecar"

আউটপুট: 2