সর্বোচ্চ দীর্ঘ রিপিটিং সাবস্ট্রিং (C++)

এই সমস্যায় একটি স্ট্রিং S দেওয়া আছে। সবচেয়ে দীর্ঘ রিপিটিং সাবস্ট্রিং-এর দৈর্ঘ্য বের করতে হবে। না থাকলে ০ ফেরত দিন।

উদাহরণ

ইনপুট: "abbaba"

আউটপুট: 2

ব্যাখ্যা: সবচেয়ে দীর্ঘ রিপিটিং সাবস্ট্রিং "ab" বা "ba" (দৈর্ঘ্য ২)।

ডাইনামিক প্রোগ্রামিং সমাধান

dp[i][j] = S[1..i] এবং S[1..j]-র সর্বোচ্চ কমন সাফিক্স দৈর্ঘ্য (যেখানে i < j)।

যদি S[i] == S[j] হয়, dp[i][j] = 1 + dp[i-1][j-1]
সর্বোচ্চ মান আপডেট করুন।

C++ প্রোগ্রাম

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

class Solution {
public:
    int longestRepeatingSubstring(string S) {
        int n = S.size();
        S = " " + S; // 1-ইন্ডেক্সড
        int ret = 0;
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (S[i] == S[j]) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1]);
                    ret = max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << ob.longestRepeatingSubstring("abbaba");
    return 0;
}