Palindromic Substring খোঁজা — Part 1: O(n³) ও O(n²) সমাধান

Palindrome কী?

যে string উল্টো করলেও একই থাকে, সেটাই palindrome।

Palindromic Substring কী?

একটা string এর ভেতরে থাকা যেকোনো continuous অংশ (substring) যেটা নিজে palindrome — সেটাই palindromic substring।

ধরো s = "abaab":

index:  0  1  2  3  4
char:   a  b  a  a  b

এর কিছু substring দেখি:

লক্ষ্য করো: "aba" আর "aa" — এই দুইটা হলো non-trivial palindromic substrings (length > 1)।

সমস্যা

একটি string s (দৈর্ঘ্য n) দেওয়া আছে। সবচেয়ে বড় palindromic substring বের করো, অথবা সকল palindromic substrings গণনা করো।

এটা solve করার জন্য ৩টা approach দেখব:

Approach 1: Brute Force — O(n³)

ধারণা

সবচেয়ে সোজা চিন্তা:

1. সম্ভাব্য সব substring বের করো → O(n²) টা pair (i, j)
2. প্রতিটা substring palindrome কিনা check করো → O(n) সময়

মোট: O(n²) × O(n) = O(n³)

Palindrome check কিভাবে?

একটা string palindrome কিনা check করতে — শুরু আর শেষ থেকে একসাথে ভেতরে আসো, প্রতিটা pair মিলাও:

bool isPalindrome(string &s, int left, int right) {
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

"abba" এর জন্য:

• s[0]='a' vs s[3]='a' → মিলে
• s[1]='b' vs s[2]='b' → মিলে
• → Palindrome!

সম্পূর্ণ O(n³) কোড

string longestPalindrome(string s) {
    int n = s.size();
    string result = "";

    for (int i = 0; i < n; i++) {           // start position
        for (int j = i; j < n; j++) {        // end position
            if (isPalindrome(s, i, j)) {     // O(n) check
                if (j - i + 1 > result.size()) {
                    result = s.substr(i, j - i + 1);
                }
            }
        }
    }
    return result;
}

কেন O(n³)?

• বাইরের দুইটা loop → সব substring enumerate করে → O(n²)
• প্রতিটার জন্য isPalindrome() → worst case O(n)
• মোট: n² × n = n³

সমস্যা কী?

n = 1000 হলে: 1000³ = 10⁹ operations — বেশিরভাগ online judge এ TLE (Time Limit Exceeded)!

আমাদের আরো ভালো কিছু দরকার।

Approach 2: Center Expansion — O(n²)

মূল ধারণা

Brute force এ আমরা প্রতিটা substring check করি। কিন্তু একটু ভিন্নভাবে চিন্তা করলে — প্রতিটা palindrome এর একটা center আছে। Center থেকে বাইরের দিকে expand করলেই palindrome পাওয়া যায়।

দুই ধরনের center

Palindrome দুই রকম হতে পারে:

1. Odd-length — center হলো একটা character:

  "a b a"
      ↑
   center = 'b'

2. Even-length — center হলো দুইটা character এর মাঝের gap:

  "a b b a"
      ↑ ↑
   center = 'b' আর 'b' এর মাঝে

Center থেকে expand কিভাবে?

ধরো center = position i। দুই পাশে একসাথে সরো:

• s[i-1] == s[i+1]? → হ্যাঁ হলে palindrome বড় হচ্ছে, আরো expand করো
• না হলে থামো

s = "abacaba", center = 3 (c):

Step 0:  _ _ _ c _ _ _    → "c" (length 1)
Step 1:  _ _ a c a _ _    → s[2]='a' == s[4]='a' ✓ → "aca" (length 3)
Step 2:  _ b a c a b _    → s[1]='b' == s[5]='b' ✓ → "bacab" (length 5)
Step 3:  a b a c a b a    → s[0]='a' == s[6]='a' ✓ → "abacaba" (length 7)
Step 4:  boundary শেষ, থামো

Even-length এর জন্য

s = "abba", center = index 1 আর 2 এর মাঝে:

Step 0:  _ b b _          → s[1]='b' == s[2]='b' ✓ → "bb" (length 2)
Step 1:  a b b a          → s[0]='a' == s[3]='a' ✓ → "abba" (length 4)
Step 2:  boundary শেষ, থামো

সম্পূর্ণ O(n²) কোড

// center থেকে দুই দিকে expand করে palindrome এর length return করে
int expandFromCenter(string &s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return right - left - 1;  // palindrome এর length
}

string longestPalindrome(string s) {
    int n = s.size();
    if (n == 0) return "";

    int start = 0, maxLen = 1;

    for (int i = 0; i < n; i++) {
        // Odd-length: center = i
        int len1 = expandFromCenter(s, i, i);

        // Even-length: center = i আর i+1 এর মাঝে
        int len2 = expandFromCenter(s, i, i + 1);

        int len = max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substr(start, maxLen);
}

কেন O(n²)?

• বাইরের loop: n টা center → O(n)
• প্রতিটা center থেকে expand: worst case O(n) (যেমন "aaaaaaa" তে প্রতিটা center থেকে পুরো string পর্যন্ত expand হবে)
• মোট: n × n = n²

O(n³) vs O(n²) তুলনা

সমস্যা কী?

n = 100,000 বা তার বেশি হলে O(n²) ও যথেষ্ট না। এক্ষেত্রে দরকার Manacher's Algorithm — O(n)!

কেন Center Expansion, Brute Force থেকে ভালো?

Brute force এ আমরা অনেক redundant কাজ করি। ধরো s[2..5] palindrome — তাহলে s[3..4] ও palindrome, কিন্তু brute force আবারো check করে!

Center expansion এই redundancy avoid করে — একবার center ঠিক করলে, ভেতর থেকে বাইরে expand করতে করতে সব nested palindromes আপনাআপনি cover হয়ে যায়।

কিন্তু center expansion এও redundancy আছে — একটা বড় palindrome এর ভেতরে থাকা ছোট palindromes এর তথ্য আমরা reuse করি না।

ধরো "abacaba" — center 3 (c) থেকে expand করে আমরা জানি পুরো string টাই palindrome। এখন center 5 (a) তে গেলে, আবার শুরু থেকে expand করি! কিন্তু center 5 তো center 3 এর palindrome এর ভেতরেই আছে — palindrome symmetric, তাই center 5 আর center 1 এর চারপাশ হুবহু একই! এই তথ্য reuse করলেই অনেক expansion skip করা যায়।

Manacher's Algorithm ঠিক এই কাজটাই করে — mirror property ব্যবহার করে আগে বের করা palindrome এর তথ্য reuse করে, আর তাই O(n) এ নেমে আসে।

এখন পর্যন্ত কোথায় আছি

Part 1 এ আমরা palindrome কী, O(n³) brute force, আর O(n²) center expansion শিখলাম। Part 2 তে দেখব কিভাবে center expansion এর redundancy দূর করে O(n) এ পৌঁছানো যায়।

Part 2 পড়ুন: Manacher's Algorithm — O(n) সমাধান