কনটেন্টে যান

001 — Reverse String

Problem link ও উৎস

  • Original source: Classic two-pointer exercise
  • Platform: LeetCode — https://leetcode.com/problems/reverse-string/
  • Topic: array / string
  • Difficulty: Easy
  • Pattern: two pointers (দুই প্রান্ত থেকে swap)
  • Basic idea inherited from: basic swap + index walk — দুটো index একসাথে হাঁটিয়ে value অদলবদল

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা character-এর array s দেওয়া আছে (যেমন ["h","e","l","l","o"])। তোমার কাজ: পুরো array টা in place উল্টে দাও — মানে নতুন কোনো array না বানিয়ে, একই array-র ভেতরেই প্রথম আর শেষ অদলবদল করতে করতে। কাজ শেষে s হয়ে যাবে ["o","l","l","e","h"]।

উদাহরণ
আগে : [h, e, l, l, o]
পরে : [o, l, l, e, h]

Input ও output

উদাহরণ
Input : ["h","e","l","l","o"]     -> Output: ["o","l","l","e","h"]
Input : ["H","a","n","n","a","h"] -> Output: ["h","a","n","n","a","H"]

Edge case 1 (একটা element): ["a"] -> ["a"]
Edge case 2 (খালি array):   []    -> []

চেনা উদাহরণে বোঝা

একসারি বইয়ের তাক ভাবো। তুমি চাও বইগুলোর order উল্টে যাক। সবচেয়ে বাঁয়ের বই আর সবচেয়ে ডানের বই হাতে নিয়ে জায়গা বদলে দাও, তারপর এক ঘর ভেতরে এসো — আবার বদলাও। মাঝে যখন দুই হাত মিলে যায়, কাজ শেষ। কোনো নতুন তাক লাগেনি।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূল ভিত হলো swap + দুই index একসাথে হাঁটানো। তুমি যদি জানো কীভাবে দুটো ঘরের value অদলবদল (a, b = b, a) করতে হয়, তাহলে পুরো reverse টা just দুই প্রান্ত থেকে সেই swap বারবার করা — একটা index বাঁ দিক থেকে ডানে, আরেকটা ডান দিক থেকে বাঁয়ে।

ভেতরের যুক্তি

লুকানো logic একটা সরল mirror-সম্পর্ক: index i-এর element-এর জায়গা হওয়া উচিত index n-1-i-তে। তাই শুধু i আর n-1-i জোড়াগুলো swap করলেই হয়। আর invariant: যেকোনো মুহূর্তে left-এর বাঁ পাশ আর right-এর ডান পাশ ইতিমধ্যে চূড়ান্ত (final) জায়গায় বসে গেছে; মাঝের অংশটুকু এখনো বাকি।

কী দিয়ে তথ্য রাখব

কোনো extra data structure লাগে না — array টা already আছে, আর শুধু দুটো integer pointer (left, right)। এটাই এর সৌন্দর্য: O(1) extra space।

এটি কেন উপযুক্ত

Array-র সবচেয়ে বড় superpower হলো index দিয়ে O(1) random access — s[left] আর s[right] দুটোতেই সরাসরি, সাথে সাথে পৌঁছানো যায় (concept.md-র mailbox analogy মনে করো)। তাই কোনো খোঁজাখুঁজি ছাড়াই দুই প্রান্তের ঘর ছুঁয়ে অদলবদল করা যায়। List mutable বলে in-place বদলানোও সম্ভব।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: একটা নতুন array নাও, পুরোনোটা শেষ থেকে শুরুর দিকে পড়ে নতুনটায় ভরো, তারপর copy করে ফেরত দাও।

উদাহরণ
new = []
for i = n-1 down to 0:
    new.append(s[i])
copy new back into s

কোথায় বেশি কাজ হচ্ছে

এটা ঠিক উত্তর দেয়, কিন্তু O(n) extra space নেয় (নতুন array)। অথচ problem চায় in-place, O(1) extra space। পুরোটা copy করা অপচয় — array টা already হাতে আছে, শুধু ভেতরে দুই প্রান্তের জোড়া swap করলেই হয়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: পুরো array একসাথে ওলটানোর দরকার নেই — শুধু symmetric জোড়াগুলো (i আর n-1-i) swap করলেই হয়। আর প্রতিটা swap-এ একসাথে দুটো element তাদের final জায়গায় বসে যায়, তাই অর্ধেক পথ হাঁটলেই (n/2 swap) পুরোটা reverse।

আরও কম কাজে সমাধান

দুটো pointer নাও — left শুরুতে 0, right শুরুতে n-1। যতক্ষণ left < right: দুটোর value swap করো, তারপর left এক ঘর ডানে, right এক ঘর বাঁয়ে। ওরা মাঝখানে দেখা করলেই কাজ শেষ।

ভাবনার পরিবর্তন

মোচড়: "array উল্টাব" ভাবার বদলে ভাবো "দুই প্রান্ত থেকে ভেতরের দিকে এসে জোড়ায় জোড়ায় swap করব।" তখন নতুন array-র দরকারই থাকে না, আর কাজও অর্ধেকে নেমে আসে।

ছবিতে বোঝা

["h","e","l","l","o"] দিয়ে দুই pointer-এর নাচ:

উদাহরণ
[ h  e  l  l  o ]
  L           R     swap h,o  -> [ o  e  l  l  h ]
     L     R        swap e,l  -> [ o  l  l  e  h ]
        LR          L == R, থামো

ফল: [ o  l  l  e  h ]

ছোট input-এ ধাপে ধাপে

Input ["h","e","l","l","o"] (n = 5):

  1. শুরু: left=0, right=4। left < right → swap s[0],s[4] (h↔o)। array: [o,e,l,l,h]। left=1, right=3।
  2. left < right → swap s[1],s[3] (e↔l)। array: [o,l,l,e,h]। left=2, right=2।
  3. left < right মিথ্যা (2 < 2 নয়) → loop শেষ।
  4. ফল: [o,l,l,e,h]।

কোড ও ব্যাখ্যা

Python

Python
def reverse_string(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]   # দুই প্রান্ত swap
        left += 1                               # left ডানে
        right -= 1                              # right বাঁয়ে
    return s

# ---- tests ----
assert reverse_string(["h", "e", "l", "l", "o"]) == ["o", "l", "l", "e", "h"]
assert reverse_string(["H", "a", "n", "n", "a", "h"]) == ["h", "a", "n", "n", "a", "H"]
assert reverse_string(["a"]) == ["a"]      # একটা element
assert reverse_string([]) == []            # খালি array
print("সব test pass!")

কোডের প্রতিটি অংশ

  • left, right = 0, len(s) - 1 — দুই pointer array-র দুই প্রান্তে বসালাম।
  • while left < right: — যতক্ষণ ওরা দেখা না করছে; সমান হলে মাঝের element নিজের জায়গাতেই থাকে, swap লাগে না।
  • s[left], s[right] = s[right], s[left] — Python-এর tuple swap, কোনো temp variable ছাড়াই অদলবদল।
  • left += 1 / right -= 1 — দুজনেই এক ঘর ভেতরে।
  • return s — একই (mutated) array ফেরত।

Output মিলিয়ে দেখা

["h","e","l","l","o"] → প্রথম swap h↔o, পরের swap e↔l, মাঝের l যেখানে আছে সেখানেই → ["o","l","l","e","h"], assert pass। বাকি case গুলোও pass। শেষে print: সব test pass!।

JavaScript ও test cases

JS-এ string immutable, তাই Python-এর মতোই char-এর array in place উল্টাই — দুই প্রান্ত থেকে swap।

JavaScript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function reverseString(s) {
  let left = 0, right = s.length - 1;
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];  // দুই প্রান্ত swap, temp ছাড়া
    left++;
    right--;
  }
  return s;
}

// ---- test cases (file-এর example + edge case) ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(reverseString(["h", "e", "l", "l", "o"]), ["o", "l", "l", "e", "h"]), "hello");
assert(eq(reverseString(["H", "a", "n", "n", "a", "h"]), ["h", "a", "n", "n", "a", "H"]), "Hannah");
assert(eq(reverseString(["a"]), ["a"]), "একটা element");
assert(eq(reverseString([]), []), "খালি array");
console.log("সব JS test pass!");

JS টীকা: JS string immutable — str[i] = ... চলে না; তাই problem char-array চায় (["h",...])। আস্ত string উল্টাতে হলে str.split("").reverse().join(""), কিন্তু সেটা O(n) extra space — in-place দুই-pointer-এর মূল শিক্ষা হারায়। swap-এ [a, b] = [b, a] (array destructuring), temp লাগে না।

TypeScript ও test cases

TypeScript
function reverseString(s: string[]): string[] {
  let left = 0, right = s.length - 1;
  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }
  return s;
}

function expectArr(actual: string[], expected: string[], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(expected)) {
    throw new Error(`FAIL ${msg}: [${actual}]`);
  }
}

expectArr(reverseString(["h", "e", "l", "l", "o"]), ["o", "l", "l", "e", "h"], "hello");
expectArr(reverseString(["a"]), ["a"], "single");
expectArr(reverseString([]), [], "empty");
console.log("সব TS test pass!");

TS টীকা: s: string[] declare করায় ভুলে একটা আস্ত string (যা JS-এ index করা গেলেও mutate হয় না) পাঠানো compile-time-এ আটকায় — in-place mutation-এর contract type-level-এই পরিষ্কার।

খরচ ও সাধারণ ভুল

সময়

O(n) — প্রায় n/2 বার swap হয়, প্রতিটা O(1); মোট O(n)।

অতিরিক্ত জায়গা

O(1) — শুধু দুটো integer pointer; array-র সাইজের সাথে extra memory বাড়ে না।

যে ভুলগুলো এড়াতে হবে

  • while left <= right লেখা — তখন মাঝের element নিজের সাথে নিজে swap হয় (ক্ষতি নেই, কিন্তু অপ্রয়োজনীয়); আসল ভুল হয় যদি এর সাথে pointer move ভুল করো।
  • নতুন array বানিয়ে ফেরত দেওয়া — তখন আর "in place" থাকে না।
  • right = len(s) দেওয়া (last index len(s)-1, len(s) নয়) → index out of range।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: array traversal + দুটো ঘরের swap। এই দুই-প্রান্ত swap-ই পরে rotate array (tracker #13)-এর triple-reversal-এর building block। chapter-এর ../patterns.md-এর "Pattern 4 — In-Place Reversal and Rotation" দেখো।

পরের অনুশীলন

কৌশলটি মনে রাখুন

Two pointers (converging): দুই প্রান্ত থেকে ভেতরের দিকে এসে জোড়ায় জোড়ায় কাজ করা — reverse, palindrome check, pair-finding-এর মূল কঙ্কাল।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "reverse in place = দুই প্রান্ত থেকে swap করে ভেতরে আসা।" যখনই দেখবে in-place উল্টাতে বা দুই প্রান্ত মেলাতে হচ্ছে, এই converging two-pointer মনে করবে — O(n) time, O(1) space।

কোথায় কাজে লাগে

  • In-place reversal building block: rotate array (তিন reversal), reverse words in a string — সবার ভিত এই দুই-প্রান্ত swap।
  • Palindrome check: দুই প্রান্ত মিলিয়ে এগোনো — একই converging two-pointer কাঠামো।
  • Buffer / byte reversal: endianness পাল্টানো, packet/buffer উল্টানো low-level-এ।
  • Undo / stack-free reversal: memory-সীমিত পরিবেশে O(1) extra space-এ ক্রম উল্টানো। মূল pattern — "দুই প্রান্ত থেকে ভেতরে এসে জোড়ায় কাজ (converging two pointers, O(1) space)" — palindrome, pair-finding, partition জুড়ে বড় ছবিতে ফেরে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।