C++-এ স্ট্রিংকে সর্বনিম্ন দৈর্ঘ্যে এনকোড করা (Encode String with Shortest Length)

ধরি আমাদের একটি খালি নন-স্ট্রিং আছে; আমাদের এই স্ট্রিংকে এনকোড করতে হবে যাতে এর এনকোডেড দৈর্ঘ্য সর্বনিম্ন হয়।

এনকোডিং নিয়ম হল: k[encoded_string], যেখানে [ ] এর ভেতরের encoded_string ঠিক k বার রিপিট হয়েছে। k একটি ধনাত্মক পূর্ণসংখ্যা এবং এনকোডেড স্ট্রিং খালি বা একস্ট্রা স্পেস নন-হবে। আমরা ধরে নিচ্ছি ইনপুট স্ট্রিং শুধু ছোট হাতের অক্ষর ধারণ করে। যদি এনকোডিং প্রসেস স্ট্রিংকে ছোট না করে, তবে সেটি এনকোড করা হবে না।

উদাহরণস্বরূপ, ইনপুট "aaaaa" হলে আউটপুট হবে "5[a]" কারণ "5[a]" "aaaaa"-র চেয়ে 1 ক্যারেক্টার ছোট।

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

একটি 2D অ্যারে dp সংজ্ঞায়িত করা।
collapse() ফাংশন সংজ্ঞায়িত করা: এটি s, i, j নিবে।
- temp := s.substr(i, j - i + 1)
- x := temp + temp
- pos = x-এ temp-এর পজিশন (1 থেকে শুরু করে)
- যদি pos >= temp.size() হয়, তবে temp ফেরত।
- অন্যথায় (temp.size() / pos) স্ট্রিং + "[" + dp[i][i+pos-1] + "]" ফেরত।
encode() ফাংশন সংজ্ঞায়িত করা: এটি s নিবে।
- n := s.size()
- dp := n x n আকারের 2D অ্যারে।
- l = 1 থেকে n পর্যন্ত লুপ:
  - i = 0, j = l-1; j < n; i++, j++:
    - dp[i][j] = s.substr(i, j - i + 1)
    - k = i থেকে j-1 পর্যন্ত লুপ:
      - temp = dp[i][k] + dp[k+1][j]
      - যদি temp.size() < dp[i][j].size() হয়, তবে dp[i][j] = temp
    - rep = collapse(s, i, j)
    - যদি rep.size() <= dp[i][j].size() হয়, তবে dp[i][j] = rep
- dp[0][n-1] ফেরত।

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

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

class Solution {
public:
    vector> dp;
    string collapse(string& s, int i, int j) {
        string temp = s.substr(i, j - i + 1);
        string x = temp + temp;
        auto pos = x.find(temp, 1);
        if (pos >= temp.size())
            return temp;
        return to_string((temp.size() / pos)) + "[" + dp[i][i + pos - 1] + "]";
    }
    string encode(string s) {
        int n = s.size();
        dp = vector>(n, vector(n, ""));
        for (int l = 1; l <= n; l++) {
            for (int i = 0, j = l - 1; j < n; i++, j++) {
                dp[i][j] = s.substr(i, j - i + 1);
                for (int k = i; k < j; k++) {
                    string temp = dp[i][k] + dp[k + 1][j];
                    if (temp.size() < dp[i][j].size()) {
                        dp[i][j] = temp;
                    }
                }
                string rep = collapse(s, i, j);
                if (rep.size() <= dp[i][j].size()) {
                    dp[i][j] = rep;
                }
            }
        }
        return dp[0][n - 1];
    }
};

int main() {
    Solution ob;
    cout << (ob.encode("bbbbbbbbbb"));
}

ইনপুট

"bbbbbbbbbb"

আউটপুট

"10[b]"