String — অক্ষরের সারি আর প্রচলিত সমস্যা

১ · String কী — অক্ষরের একটি সারি

ধরুন বাসের টিকিট কাউন্টারে যাত্রীর নাম লেখা হচ্ছে একটি খাতায়, প্রতিটি ঘরে একটি করে অক্ষর: R, A, H, I, M. ঘরগুলো পাশাপাশি, প্রতিটির একটি নম্বর আছে — ০, ১, ২, ৩, ৪. তৃতীয় অক্ষর কী, জানতে চাইলে খাতাওয়ালাকে পুরো নাম পড়তে হয় না; সরাসরি ২ নম্বর ঘরে আঙুল রাখলেই হয়।

এটাই string: character (অক্ষর)-এর একটি ক্রমিক সারি। মেমরিতে string আসলে একটি array — পর্ব ১০-এ যে অ্যারে দেখেছেন, তারই একটি বিশেষ রূপ, যার প্রতিটি ঘরে একটি অক্ষরের কোড। তাই অ্যারের সব নিয়ম এখানেও খাটে:

দৈর্ঘ্য জানা O(1) — এটি কিন্তু স্বতঃসিদ্ধ নয়। C ভাষায় string হলো শুধু char-এর অ্যারে, যার শেষে একটি বিশেষ অক্ষর '\0' বসানো থাকে — একে বলে null terminator. দৈর্ঘ্য কোথাও লেখা থাকে না, তাই strlen প্রতিবার শুরু থেকে হেঁটে '\0' খোঁজে: O(n). লুপের শর্তে for (i = 0; i < strlen(s); i++) লিখলে প্রতিটি ঘুর্ণনে আবার পুরো string হাঁটা হয় — নিরীহ চেহারার একটি লুপ হয়ে যায় O(n²). C++-এর std::string আর Python-এর str দৈর্ঘ্য আলাদা করে মনে রাখে, তাই এই ফাঁদ সেখানে নেই।

এই পর্বের প্রায় সব সমস্যা একটি প্রশ্নের চারপাশে ঘোরে: কোন কাজে পুরো string হাঁটতে বা কপি করতে হয়, আর কোনটিতে হয় না? উত্তরটা পরিষ্কার থাকলে string-এর প্রায় সব complexity নিজেই বের করতে পারবেন।

২ · বদলানো যায়, না যায় না — mutable বনাম immutable

C++-এ string s = "cat"; s[0] = 'b'; লিখলে s হয়ে যায় "bat" — একই মেমরিতে, জায়গায় বসেই বদল। এমন বস্তুকে বলে mutable. Python-এ একই কাজ s[0] = 'b' করতে গেলে আসে TypeError: 'str' object does not support item assignment. Python-এর str (আর Java-র String) immutable: একবার তৈরি হলে আর বদলায় না। “বদলাতে” চাইলে নতুন একটি string বানাতে হয় — যেমন s = 'b' + s[1:].

বারবার জোড়া দেওয়ার O(n²) ফাঁদ

দুটি string জোড়া দেওয়া — string concatenation — দেখতে এক অপারেশন, কিন্তু নতুন string বানাতে দুটির সব অক্ষর নতুন জায়গায় কপি করতে হয়। এখন ধরুন একটি লুপে একটি করে অক্ষর যোগ করে "Dhaka" বানাচ্ছেন, প্রতিবার s = s + c লিখে। immutable string-এ প্রতিটি ধাপে কী ঘটে, দেখুন:

৫ অক্ষরে ১৫ বনাম ৫ — তুচ্ছ পার্থক্য। কিন্তু ১ লাখ (10⁵) অক্ষরের লগ-ফাইল বা আউটপুট এভাবে বানালে + পদ্ধতিতে কপি প্রায় 5 × 10⁹ — কয়েক সেকেন্ড থেকে মিনিট; join-এ মাত্র 10⁵. কনটেস্টে বড় আউটপুট ছাপার সময় এই ভুলেই অনেক সমাধান “Time Limit Exceeded” পায়। এই ধরনের quadratic খরচ কোডে চোখে পড়ে না, কারণ লাইনটি দেখতে মাত্র একটি +.

সমাধানের মূল কৌশলের নাম string builder: টুকরোগুলো আগে একটি বাড়তে-পারা জায়গায় জমান, শেষে একবারে string বানান। প্রতিটি ভাষায় এর নিজস্ব রূপ:

string out;
out.reserve(n);                  // optional: allocate once up front
for (int i = 0; i < n; ++i)
    out += piece(i);             // GOOD: appends in place, amortized O(1) per char

// out = out + piece(i);         // BAD: builds a temporary copy every time -> O(n^2)

ostringstream os;                // also fine for mixed numbers and text
os << "id=" << 42 << ", score=" << 7.5;
string line = os.str();

parts = []
for i in range(n):
    parts.append(piece(i))       # GOOD: list append, amortized O(1)
out = "".join(parts)             # one pass, total length computed first

# out = out + piece(i)           # risky: may copy everything each time -> O(n^2)

print("\n".join(map(str, answers)))   # fast way to print many lines

৩ · অক্ষর আসলে সংখ্যা — ASCII, Unicode আর UTF-8

কম্পিউটার অক্ষর চেনে না, চেনে শুধু সংখ্যা। প্রতিটি অক্ষরকে একটি নম্বর দেওয়ার চুক্তির নাম character encoding. সবচেয়ে পুরোনো জনপ্রিয় চুক্তি ASCII (১৯৬৩): ৭ bit, মোট ১২৮টি অক্ষর। কয়েকটি মান মুখস্থ রাখলে DSA-র অনেক কৌশল সহজ হয়:

বড় আর ছোট হাতের একই অক্ষরের পার্থক্য ঠিক ৩২ ('a' - 'A') — তাই case বদলানো একটি যোগ-বিয়োগ মাত্র। কিন্তু ১২৮টি ঘরে বাংলা, আরবি, চীনা লিপির জায়গা নেই। সেই সমস্যার সমাধান Unicode: পৃথিবীর প্রায় সব লিপির প্রতিটি অক্ষরকে একটি অনন্য নম্বর, যার নাম code point. যেমন A = U+0041, ক = U+0995, ই-কার ি = U+09BF. বাংলা লিপির পুরো ব্লক U+0980 থেকে U+09FF.

নম্বর তো হলো, কিন্তু সেটি বাইটে লেখা হবে কীভাবে? সবচেয়ে প্রচলিত উত্তর UTF-8: ASCII অক্ষর আগের মতোই ১ বাইটে, অন্যগুলো ২, ৩ বা ৪ বাইটে। প্রতিটি বাইটের শুরুর bit দেখেই বোঝা যায় সেটি কোন ভূমিকায়:

এবার দেখুন C++-এর একটি std::string-এ "Aকি" লেখাটি (ফাইল UTF-8-এ সেভ করা) মেমরিতে আসলে কী, আর একটি প্রোগ্রাম বাইটগুলো পড়ে কীভাবে অক্ষর ফিরে পায়:

এর বাস্তব পরিণতি কয়েকটি, এবং বাংলায় কাজ করলে এগুলো রোজ সামনে আসবে:

• C++-এ s[i] বাংলা অক্ষর দেয় না, দেয় একটি বাইট। s.substr(0, 2) একটি বাংলা অক্ষরকে মাঝখান থেকে কেটে অবৈধ বাইট-টুকরো বানায় — স্ক্রিনে আসে �. একইভাবে বাইট ধরে string উল্টালে বাংলা লেখা ভেঙে যায়।
• code point গুনতে শুধু সেই বাইটগুলো গুনুন যেগুলো ধারাবাহিক নয়: (c & 0xC0) != 0x80. এটি O(n), কারণ প্রতিটি বাইট একবার দেখতে হয়।
• Python-এ len("বাংলা") = ৫, কারণ ব, া, ং, ল, া — পাঁচটি code point; পাঠক দেখেন মোটে দু-তিনটি “অক্ষর”। যুক্তাক্ষর ক্ষ = ক + ্ (হসন্ত) + ষ — তিনটি code point, UTF-8-এ ৯ বাইট, চোখে একটি।
• Python-এ s[i] O(1)-এই code point দেয়, কারণ CPython ভেতরে লেখাটিকে প্রতি অক্ষরে সমান মাপে (১, ২ বা ৪ বাইট) রাখে; UTF-8-এ রাখলে i-তম অক্ষর খুঁজতে শুরু থেকে হাঁটতে হতো।

৪ · তুলনা, অভিধানের ক্রম আর substring-এর খরচ

ফোনবুকে “Rahim” আগে না “Rahima”? “Karim” না “Kamal”? আমরা জানি — অভিধানের নিয়মে। এই নিয়মের নাম lexicographic order, আর C++ ও Python দুটোতেই s < t ঠিক এটাই করে:

1. বাঁ দিক থেকে একটি একটি করে অক্ষর মেলান।
2. প্রথম যে ঘরে অক্ষর আলাদা, সেই দুটি অক্ষরের কোড তুলনা করুন — যার কোড ছোট, সেই string আগে। "Kamal" < "Karim", কারণ তৃতীয় ঘরে 'm' (109) < 'r' (114).
3. একটি string শেষ হয়ে গেলে আর অমিল না পেলে — ছোটটি আগে। "Rahim" < "Rahima".

খরচ: সবচেয়ে খারাপে min(n, m) টি তুলনা — অর্থাৎ O(min(n, m)). এটি মনে রাখা জরুরি, কারণ অনেকে string তুলনাকে O(1) ধরে complexity হিসাব করেন। n টি string sort করলে তুলনা হয় O(n log n) বার (পর্ব ২১), আর প্রতিটি তুলনা O(L) পর্যন্ত, যেখানে L গড় দৈর্ঘ্য — মোট O(L · n log n).

তৃতীয় সারিটি বাস্তবে প্রায়ই ঝামেলা করে: ফাইলের নাম file10.txt চলে আসে file9.txt-এর আগে, রোল নম্বর string হিসেবে রাখলে “১০” বসে “৯”-এর আগে। সমাধান: সংখ্যা সংখ্যা হিসেবে রাখুন, অথবা সব রোল সমান দৈর্ঘ্যে লিখুন ("009", "010"). বাংলা শব্দের ক্রমে আরেকটি সমস্যা আছে — code point-এর ক্রম সবসময় বাংলা অভিধানের ক্রম নয়; ভাবনার প্রশ্ন ৩-এ সেটি দেখবেন।

Substring — দেখতে ছোট, খরচ লুকানো

একটি string-এর ভেতরের পাশাপাশি অক্ষরের টুকরো হলো substring. শুরু থেকে নেওয়া টুকরো prefix, শেষ পর্যন্ত নেওয়া টুকরো suffix. n দৈর্ঘ্যের string-এ খালি বাদে substring মোট n(n+1)/2 টি — তাই “সব substring পরীক্ষা করো” মানেই অন্তত O(n²), আর প্রতিটির ভেতরে কাজ থাকলে আরও বেশি।

সবচেয়ে সাধারণ ফাঁদ: s.substr(i, k) (C++) বা s[i:i+k] (Python) একটি নতুন কপি বানায় — খরচ O(k), O(1) নয়। লুপের ভেতরে বারবার slice নিলে লুকানো একটি বাড়তি গুণক যোগ হয়। পর্ব ০৭-এ দেখেছেন, রিকার্শনে s[1:] পাঠালে কীভাবে O(n) কাজ O(n²) হয়ে যায়।

string s = "dhanmondi";
string a = s.substr(0, 4);         // copies 4 chars: "dhan"       O(k)
string_view v(s);                  // no copy: pointer + length     O(1)
string_view b = v.substr(0, 4);    // still no copy: "dhan"         O(1)
// careful: b is only valid while s is alive and unchanged

C++17-এর std::string_view কপি না করে মূল string-এর একটি অংশের দিকে শুধু “তাকিয়ে” থাকে — শুরুর ঠিকানা আর দৈর্ঘ্য। তাই এর substr O(1). বিনিময়ে একটি দায়িত্ব: মূল string মুছে গেলে বা বদলালে view-টি অবৈধ (dangling) হয়ে যায়। Python-এ সরাসরি এর সমতুল্য নেই; সেখানে প্রচলিত কৌশল হলো slice না নিয়ে শুরু আর শেষের index পাঠানো।

৫ · অক্ষর গোনা — ২৬ ঘরের অ্যারে আর map

পরীক্ষার হলে খাতা জমা নেওয়ার সময় শিক্ষক প্রতিটি রোল নম্বরের পাশে টিক দেন — কেউ বাদ পড়ল কি না, কেউ দুবার জমা দিল কি না। string-এর বহু সমস্যার সমাধান ঠিক এভাবে: প্রতিটি অক্ষর কতবার এসেছে, গুনে ফেলুন।

ইনপুট যদি শুধু ইংরেজি ছোট হাতের অক্ষর হয় ('a' থেকে 'z'), তাহলে ২৬ ঘরের একটি অ্যারেই যথেষ্ট — অক্ষর c-এর ঘর হলো c - 'a' ('a' → 0, 'c' → 2, 'r' → 17). একে বলে frequency array. অক্ষরের জগৎ বড় বা অজানা হলে (বাংলা, Unicode, পুরো শব্দ) অ্যারের বদলে hash table — C++-এ unordered_map, Python-এ dict বা collections.Counter (পর্ব ১৫, ৩২).

Anagram — একই অক্ষর, ভিন্ন ক্রম

listen আর silent — একই ছয়টি অক্ষর, শুধু ক্রম আলাদা। এমন জোড়াকে বলে anagram. সরল উপায়: দুটিকেই sort করে মেলানো — O(n log n). গোনার উপায় আরও দ্রুত: প্রথম string-এর প্রতিটি অক্ষরে ঘর +১, দ্বিতীয়টির প্রতিটিতে −১. শেষে সব ঘর ০ হলেই anagram. নিচে "arc" আর "car":

1bool isAnagram(const string& s, const string& t) {2    if (s.size() != t.size()) return false;3    array<int, 26> cnt{};             // all zero4    for (char c : s) cnt[c - 'a']++;5    for (char c : t)6        if (--cnt[c - 'a'] < 0) return false;7    return true;8}

কেন ঠিক কাজ করে? দৈর্ঘ্য সমান হলে দুটির মোট গণনাও সমান। দ্বিতীয় লুপ শেষে যদি কোনো ঘর ধনাত্মক থাকত, তাহলে মোট সমান রাখতে অন্য কোনো ঘর অবশ্যই ঋণাত্মক হতো — আর সেটি আমরা লুপের ভেতরেই ধরে ফেলতাম। তাই “কোনো ঘর ঋণাত্মক হয়নি” মানেই সব ঘর 0. এক লাইনের এই যুক্তিটিই শেষে আলাদা করে সব ঘর পরীক্ষা করার দরকার মিটিয়ে দেয়।

প্রথম অনন্য অক্ষর

প্রশ্ন: string-এ প্রথম যে অক্ষরটি মাত্র একবার এসেছে, তার index কত? ("swiss" → 1, কারণ 'w'; কোনোটি না থাকলে −1.) প্রতিটি অক্ষরের জন্য বাকি string খুঁজলে O(n²). গোনার কৌশলে দুটি পাস যথেষ্ট:

def first_unique(s):
    cnt = [0] * 26
    for c in s:                          # pass 1: count everything
        cnt[ord(c) - ord('a')] += 1
    for i, c in enumerate(s):            # pass 2: first char with count 1
        if cnt[ord(c) - ord('a')] == 1:
            return i
    return -1                            # first_unique("swiss") == 1

সময় O(n) (দুটি পাস), জায়গা O(1). প্রথম পাসে আগে পুরো তথ্য জমান, দ্বিতীয় পাসে সিদ্ধান্ত নিন — “আগে গোনো, পরে সিদ্ধান্ত” ধাঁচটি পর্ব ২৪-এর counting sort-এরও ভিত্তি।

৬ · Palindrome আর উল্টানো — দুই প্রান্ত থেকে দুই পয়েন্টার

level, racecar, বাংলায় “রমাকান্তকামার” — সামনে থেকে আর পেছন থেকে পড়লে একই। (বাংলা উদাহরণটি অবশ্য চোখে দেখা অক্ষর ধরে palindrome: র-মা-কা-ন্ত-কা-মা-র; code point ধরে উল্টালে মেলে না, কারণ কার-চিহ্ন আর হসন্ত আলাদা code point — অংশ ৩ মনে করুন।) এমন লেখাকে বলে palindrome. একটি উপায়: string উল্টে মূলটির সাথে মেলানো — O(n) সময়, কিন্তু উল্টানো কপির জন্য O(n) বাড়তি জায়গা। ভালো উপায় two pointers: একটি index i শুরুতে, আরেকটি j শেষে; দুটি অক্ষর মিললে দুজনই এক ঘর ভেতরে আসে, না মিললেই উত্তর “না”।

ইন্টারভিউর সংস্করণে সাধারণত একটি শর্ত থাকে: শুধু অক্ষর আর অঙ্ক গণ্য, ফাঁকা জায়গা আর চিহ্ন বাদ, বড়-ছোট হাতের পার্থক্য নেই। নিচে "Top spot" (_ = ফাঁকা জায়গা):

শুদ্ধতার যুক্তি (loop invariant, পর্ব ০৩): প্রতিটি ঘুর্ণনের শুরুতে সত্য — “i-এর বাঁয়ের আর j-এর ডানের অংশ (শুধু অক্ষর-অঙ্ক ধরে) একে অপরের আয়না”। শুরুতে দুটি অংশই খালি, তাই সত্য। মিলের পর দুজন ভেতরে এলে সত্য থাকে; চিহ্ন বাদ দিলে আয়নায় কিছু যোগ হয় না। লুপ থামলে বাকি থাকে বড়জোর একটি অক্ষর, যা নিজের আয়না — তাই পুরো লেখা palindrome. এই দুই-প্রান্ত কৌশলের আরও বহু প্রয়োগ (sorted অ্যারেতে জোড়া খোঁজা, sliding window) আসবে পর্ব ১৬-এ।

শব্দগুলো উল্টানো

প্রশ্ন: "the sky is blue" → "blue is sky the". Python-এ এক লাইন: " ".join(reversed(s.split())) — split() বাড়তি ফাঁকা জায়গাও বাদ দেয়, সময় O(n), জায়গা O(n). C++-এ mutable string থাকায় একটি সুন্দর in-place কৌশল আছে: আগে পুরো string উল্টান, তারপর প্রতিটি শব্দ আলাদা করে উল্টান।

// "the sky is blue" -> "eulb si yks eht" -> "blue is sky the"
void reverseWords(string& s) {          // assumes single spaces between words
    reverse(s.begin(), s.end());         // step 1: whole string
    size_t start = 0;
    for (size_t i = 0; i <= s.size(); ++i)
        if (i == s.size() || s[i] == ' ') {
            reverse(s.begin() + start, s.begin() + i);   // step 2: each word
            start = i + 1;
        }
}

প্রতিটি অক্ষর মোট দুবার সরে (একবার পুরো উল্টানোয়, একবার শব্দ উল্টানোয়), তাই সময় O(n), বাড়তি জায়গা O(1). এই “দুবার উল্টাও” কৌশল অ্যারে k ঘর ঘোরাতেও (rotate) কাজে লাগে।

এবার anagram আর palindrome দুটো যাচাই একসাথে চালিয়ে দেখুন। দুটি ভাষাতেই একই ইনপুট, একই আউটপুট:

#include <array>
#include <cctype>
#include <initializer_list>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
bool isAnagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;        // counts of 'a'..'z' must match
    array<int, 26> cnt{};
    for (char c : s) cnt[c - 'a']++;
    for (char c : t) if (--cnt[c - 'a'] < 0) return false;   // t has an extra c
    return true;
}

bool isPalindrome(const string& s) {               // two pointers, ignore case
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        unsigned char a = s[i], b = s[j];
        if (!isalnum(a)) ++i;                      // skip space, comma, colon
        else if (!isalnum(b)) --j;
        else if (tolower(a) != tolower(b)) return false;
        else { ++i; --j; }
    }
    return true;
}

int main() {
    vector<pair<string, string>> tests = {{"listen", "silent"}, {"arc", "car"}, {"aab", "abb"}, {"hello", "world"}};
    for (auto& [a, b] : tests)
        cout << a << " / " << b << " -> " << (isAnagram(a, b) ? "anagram" : "not anagram") << '\n';
    for (string s : {"Top spot", "A man, a plan, a canal: Panama", "abca", ""})
        cout << '"' << s << "\" -> " << (isPalindrome(s) ? "palindrome" : "not palindrome") << '\n';
}

listen / silent -> anagram
arc / car -> anagram
aab / abb -> not anagram
hello / world -> not anagram
"Top spot" -> palindrome
"A man, a plan, a canal: Panama" -> palindrome
"abca" -> not palindrome
"" -> palindrome

def is_anagram(s, t):
    if len(s) != len(t):                 # counts of 'a'..'z' must match
        return False
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - ord('a')] += 1
    for c in t:
        k = ord(c) - ord('a')
        cnt[k] -= 1
        if cnt[k] < 0:                   # t has an extra c
            return False
    return True

def is_palindrome(s):                    # two pointers, ignore case
    i, j = 0, len(s) - 1
    while i < j:
        if not s[i].isalnum():           # skip space, comma, colon
            i += 1
        elif not s[j].isalnum():
            j -= 1
        elif s[i].lower() != s[j].lower():
            return False
        else:
            i, j = i + 1, j - 1
    return True

for a, b in [("listen", "silent"), ("arc", "car"), ("aab", "abb"), ("hello", "world")]:
    print(f"{a} / {b} -> {'anagram' if is_anagram(a, b) else 'not anagram'}")
for s in ["Top spot", "A man, a plan, a canal: Panama", "abca", ""]:
    print(f'"{s}" -> {"palindrome" if is_palindrome(s) else "not palindrome"}')

listen / silent -> anagram
arc / car -> anagram
aab / abb -> not anagram
hello / world -> not anagram
"Top spot" -> palindrome
"A man, a plan, a canal: Panama" -> palindrome
"abca" -> not palindrome
"" -> palindrome

৭ · String থেকে সংখ্যা, সংখ্যা থেকে string

ইনপুট ফাইল, ওয়েব ফর্ম, bKash-এর SMS — সব জায়গায় সংখ্যা আসে লেখা হিসেবে: "4096". হিসাব করতে হলে আগে সেটিকে আসল সংখ্যায় আনতে হয়। লেখা পড়ে মান বের করার এই কাজের নাম parsing. ভেতরের কৌশলটি খুব সরল — বাঁ থেকে প্রতিটি অঙ্ক পড়ে, এ পর্যন্ত পাওয়া মানকে ১০ দিয়ে গুণ করে নতুন অঙ্ক যোগ করুন:

long long parseNumber(const string& s) {        // assumes only digits '0'..'9'
    long long num = 0;
    for (char c : s)
        num = num * 10 + (c - '0');             // "4096": 4 -> 40 -> 409 -> 4096
    return num;
}
string toText(long long x) {                    // the reverse: peel digits off the end
    if (x == 0) return "0";
    string r;
    for (; x > 0; x /= 10) r += char('0' + x % 10);   // "6904"
    reverse(r.begin(), r.end());                // -> "4096"
    return r;
}

c - '0' কেন অঙ্কের মান দেয়? কারণ ASCII-তে '0' থেকে '9' পরপর 48 থেকে 57 — '7' - '0' = 55 − 48 = 7. দুটি ফাংশনই প্রতি অঙ্কে O(1) কাজ করে, তাই d অঙ্কের সংখ্যায় O(d) = O(log x). উল্টো দিকে লক্ষ করুন: অঙ্কগুলো শেষ থেকে আসে (x % 10), তাই শেষে একবার উল্টাতে হয় — প্রতিবার সামনে যোগ করলে (r = c + r) আবার সেই O(d²) জোড়ার ফাঁদ।

বাস্তবে নিজে না লিখে লাইব্রেরি ব্যবহার করবেন। কিন্তু লাইব্রেরির আচরণ ভাষাভেদে আলাদা, আর পরীক্ষায় ঠিক এগুলোই জিজ্ঞেস করা হয়:

৮ · ইন্টারভিউর দুই ক্লাসিক — common prefix আর compression

Longest common prefix

ঢাকার কয়েকটি এলাকার নাম: dhaka, dhanmondi, dhamrai. সবার শুরুতে যে সবচেয়ে লম্বা অংশ হুবহু এক, তা হলো dha — একে বলে longest common prefix (LCP). ফোনের কন্ট্যাক্টে বা সার্চ বক্সে টাইপ করার সময় যে “স্বয়ংক্রিয় পূরণ” দেখেন, তার পেছনে এই ধারণা (পর্ব ৩১-এর trie এটিকে আরও দক্ষ করে)।

সহজ পদ্ধতি — কলাম ধরে মেলানো: সব শব্দের ঘর 0 মেলে? তাহলে ঘর 1 দেখুন… যে কলামে প্রথম অমিল বা কোনো শব্দ শেষ, সেখানেই থামুন। k শব্দ আর উত্তরের দৈর্ঘ্য p হলে কাজ O(k·(p + 1)). প্রতিটি শব্দ অন্তত p অক্ষরের, তাই k·p ≤ S (সব অক্ষরের মোট সংখ্যা) — অর্থাৎ কাজ O(S + k). মৌলিকভাবে এর চেয়ে ভালো সম্ভব নয়, কারণ উত্তর নিশ্চিত হতে হলে প্রতিটি শব্দের প্রথম p টি অক্ষর দেখতেই হয় — Ω(k·p).

Run-length compression — “aaabb” → “a3b2”

বাসের কন্ডাক্টর যাত্রী গোনেন না একজন একজন করে নাম ধরে — বলেন “গুলিস্তানের ৩ জন, ফার্মগেটের ২ জন”। একই অক্ষরের টানা সারিকে (run) “অক্ষর + কতবার” দিয়ে লেখার এই কৌশলের নাম run-length encoding (RLE). অ্যালগরিদম এক পাসের: i থেকে শুরু করে j-কে ডানে সরান যতক্ষণ একই অক্ষর; তারপর লিখুন s[i] আর j − i, আর i-কে j-তে নিয়ে যান।

Pseudocode (0-based index)

COMPRESS(s):                       // n = length of s
    out = empty builder
    i = 0
    while i < n:
        j = i
        while j < n and s[j] == s[i]:
            j = j + 1              // s[i..j-1] is one run
        append s[i] and (j - i) to out
        i = j                      // jump to the next run
    return out as a string

ভেতরে দুটি নেস্টেড লুপ দেখে অনেকে বলেন O(n²) — ভুল। j কখনো পেছনে যায় না, আর i সরাসরি j-তে লাফ দেয়; তাই j মোট n বার বাড়ে, পুরো কাজ O(n). নেস্টেড লুপ মানেই O(n²) নয় — ভেতরের পয়েন্টার মোট কতবার সরে, সেটি গুনুন। এখানে লেখার জন্য builder ব্যবহার না করে out = out + ... লিখলে আবার অংশ ২-এর O(n²) ফাঁদে পড়তেন।

#include <initializer_list>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string compress(const string& s) {             // "aaabb" -> "a3b2"
    string out;
    out.reserve(2 * s.size());                  // worst case "abc" -> "a1b1c1"
    for (size_t i = 0; i < s.size(); ) {
        size_t j = i;
        while (j < s.size() && s[j] == s[i]) ++j;   // s[i..j-1] is one run
        out += s[i];
        out += to_string(j - i);                // += appends in place
        i = j;
    }
    return out;
}

string lcp(const vector<string>& words) {      // check column k of every word
    if (words.empty()) return "";
    for (size_t k = 0; ; ++k)
        for (const string& w : words)
            if (k == w.size() || w[k] != words[0][k]) return words[0].substr(0, k);
}

int main() {
    for (string s : {"aaabb", "abc", "aaaaaaaaaaaab", "zzzzzz"})
        cout << s << " -> " << compress(s) << '\n';
    for (const vector<string>& ws : {vector<string>{"flower", "flow", "flight"},
                                    vector<string>{"dhaka", "dhanmondi", "dhamrai"},
                                    vector<string>{"bus", "train"}})
        cout << "lcp = \"" << lcp(ws) << "\"\n";
}

aaabb -> a3b2
abc -> a1b1c1
aaaaaaaaaaaab -> a12b1
zzzzzz -> z6
lcp = "fl"
lcp = "dha"
lcp = ""

def compress(s):                         # "aaabb" -> "a3b2"
    out = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1                       # s[i:j] is one run
        out.append(s[i] + str(j - i))
        i = j
    return "".join(out)                  # one final copy, not n copies

def lcp(words):                          # check column k of every word
    if not words:
        return ""
    k = 0
    while True:
        for w in words:
            if k == len(w) or w[k] != words[0][k]:
                return words[0][:k]
        k += 1

for s in ["aaabb", "abc", "aaaaaaaaaaaab", "zzzzzz"]:
    print(f"{s} -> {compress(s)}")
for ws in [["flower", "flow", "flight"], ["dhaka", "dhanmondi", "dhamrai"], ["bus", "train"]]:
    print(f'lcp = "{lcp(ws)}"')

aaabb -> a3b2
abc -> a1b1c1
aaaaaaaaaaaab -> a12b1
zzzzzz -> z6
lcp = "fl"
lcp = "dha"
lcp = ""

৯ · লেখার ভেতরে খোঁজা — সরল pattern matching আর hashing-এর আভাস

ব্রাউজারে Ctrl+F চাপলেন, লিখলেন “bKash” — পুরো পাতায় শব্দটি কোথায় কোথায় আছে, মুহূর্তে হলুদ হয়ে যায়। এই কাজের নাম pattern matching: n দৈর্ঘ্যের একটি লেখা (text) T-এর ভেতরে m দৈর্ঘ্যের pattern P কোথায় কোথায় হুবহু আছে, খুঁজে বের করা। সবচেয়ে সরল উপায় — naive string matching: P-কে T-এর প্রতিটি সম্ভাব্য শুরুর ঘরে (shift) বসিয়ে বাঁ থেকে অক্ষর মেলান; অমিল পেলেই পরের shift.

এখানে বেশিরভাগ shift প্রথম অক্ষরেই বাতিল হয়েছে, তাই কাজ কম। কিন্তু সবচেয়ে খারাপ ইনপুটটি ভাবুন: T = "aaaa…a" (n টি a), P = "aa…ab" (m − 1টি a, শেষে b). প্রতিটি shift-এ প্রথম m − 1টি তুলনা মেলে, শেষটিতে অমিল — মোট প্রায় (n − m + 1)·m তুলনা। n = 10⁶ আর m = 10⁵ হলে প্রায় 9 × 10¹⁰ — কনটেস্টের সময়সীমায় অসম্ভব।

Pseudocode (0-based index)

NAIVE-MATCH(T, P):                 // n = |T|, m = |P|
    for s = 0 to n - m:            // every possible shift
        k = 0
        while k < m and T[s + k] == P[k]:
            k = k + 1
        if k == m:
            report a match at s    // O((n - m + 1) * m) in the worst case

অপচয়টি কোথায়, stepper-এর ধাপ ২-এ দেখেছেন: প্রতিটি অমিলের পর আমরা আগে মেলানো সব তথ্য ফেলে দিয়ে আবার শূন্য থেকে শুরু করি। দ্রুত অ্যালগরিদমগুলো ঠিক এই অপচয় বন্ধ করে। KMP (Knuth–Morris–Pratt, ১৯৭৭ সালে প্রকাশিত) আর Z algorithm pattern-এর নিজের গঠন আগে থেকে বিশ্লেষণ করে রাখে, যাতে অমিলের পর কতদূর লাফ দেওয়া নিরাপদ তা জানা থাকে — সবচেয়ে খারাপেও O(n + m). সেগুলোর পুরো আলোচনা পর্ব ৫৮-এ।

String hashing — লেখাকে একটি সংখ্যায় বদলানো

আরেকটি ভিন্ন চিন্তা: দুটি m দৈর্ঘ্যের string অক্ষর ধরে মেলাতে O(m) লাগে। কিন্তু যদি প্রতিটি string-কে একটি সংখ্যা দিয়ে প্রকাশ করা যেত, তাহলে তুলনা হতো O(1). এটিই string hashing-এর মূল ধারণা। প্রচলিত polynomial hash অক্ষরগুলোকে একটি base B-এর অঙ্ক হিসেবে ধরে, বড় একটি মৌলিক সংখ্যা M-এর mod-এ (পর্ব ৬২):

অংশ ৭-এর num = num * 10 + d-এর সাথে মিল দেখছেন? এটি হুবহু সেই সূত্র, শুধু ১০-এর বদলে B আর প্রতি ধাপে mod. আসল জাদু rolling hash-এ: text-এর ওপর m দৈর্ঘ্যের জানালা এক ঘর সরালে বাঁয়ের অক্ষরের অবদান বাদ দিয়ে, B দিয়ে গুণ করে, ডানের অক্ষর যোগ করলেই নতুন hash — O(1)-এ। ফলে প্রতিটি shift-এর hash মোট O(n)-এ পাওয়া যায়; এই ধারণার ওপর দাঁড়িয়ে Rabin–Karp অ্যালগরিদম। সতর্কতা একটিই: দুটি ভিন্ন string-এর hash মিলে যেতে পারে — একে বলে collision — তাই hash মিললে হয় অক্ষর ধরে যাচাই করুন, নয়তো বড় বা দুটি আলাদা M ব্যবহার করে ভুলের সম্ভাবনা নগণ্য করুন। বিস্তারিত পর্ব ৫৮-এ; hash table-এর দিক থেকে hash function-এর আলোচনা পর্ব ৩২-এ।

১০ · AI-এর যুগে string — ছোট কোড, লুকানো খরচ

string-এর সমস্যায় AI-এর লেখা কোড সাধারণত ছোট, পরিষ্কার আর উদাহরণে নির্ভুল। ভুল লুকিয়ে থাকে তিন জায়গায়: লুকানো কপি (slice, +, substr) যা complexity বাড়িয়ে দেয়, কিনারার ইনপুট (খালি string, এক অক্ষর, ১০+ পুনরাবৃত্তি, বড় হাতের অক্ষর), আর এনকোডিং — বিশেষ করে বাংলা বা emoji এলে।

String-এর সমস্যায় AI সাধারণত যেসব ভুল করে

AI-এর (বা নিজের) string কোড যাচাইয়ের চেকলিস্ট

• খালি string, এক অক্ষর আর সব অক্ষর এক ("zzzz") — তিনটিতেই চালিয়েছি
• প্রতিটি +, slice আর substr-এর খরচ ধরে complexity নিজে হিসাব করেছি
• ছোট উদাহরণে (৫–৮ অক্ষর) হাতে পয়েন্টার বা গণনা-অ্যারে trace করে ফল মিলিয়েছি
• ইনপুটের অক্ষরের জগৎ (শুধু a–z? বড় হাতের? Unicode?) সমস্যার শর্তের সাথে মিলিয়েছি
• n দ্বিগুণ করে সময় মেপেছি — দ্বিগুণ হলে O(n), চারগুণ হলে O(n²)
• এলোমেলো ছোট ইনপুটে একটি সরল brute force সমাধানের সাথে মিলিয়ে stress testing করেছি