Skip to content

003 — Reverse String

Source

  • Original source: Classic recursion exercise
  • Platform: LeetCode — https://leetcode.com/problems/reverse-string/
  • Topic: recursion (decrease-and-conquer, two ends)
  • Difficulty: Easy
  • Pattern: decrease-and-conquer — swap বাইরের জোড়া, ভেতরের দিকে recurse
  • Basic idea inherited from: swap + ভেতরের দিকে recurse

1. Problem in simple words

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

আগে : ['h', 'e', 'l', 'l', 'o']
পরে : ['o', 'l', 'l', 'e', 'h']

2. Which basic idea does this inherit from?

ভিত্তি হলো swap + ভেতরের দিকে recurse। তুমি যদি জানো কীভাবে দুটো প্রান্তের element অদলবদল করতে হয়, তাহলে পুরো reverse just সেই swap-টা করে এক ধাপ ভেতরে ঢুকে আবার সেই একই কাজ করা। প্রতিটা recursive call problem-টাকে দুই দিক থেকে ছোট করে — এটাই decrease-and-conquer-এর "two ends" রূপ।

3. What is the hidden math or logic?

লুকানো logic একটা invariant: বাইরের দিকের সব জোড়া ইতিমধ্যে ঠিক জায়গায় বসে গেছে, আর left ও right-এর মাঝের অংশটুকু এখনো উল্টানো বাকি। প্রতিটা swap একটা জোড়া fix করে, তারপর left+1, right-1 দিয়ে recurse করায় বাকি অংশ এক ধাপ ছোট হয়। left >= right হলে আর কিছু উল্টানোর নেই।

4. Which data structure is needed?

কোনো extra data structure লাগে না — input list (array) নিজেই যথেষ্ট। শুধু দুটো index pointer (left, right) আর recursion-এর জন্য call stack। In-place হওয়ায় এটাই সৌন্দর্য।

5. Why this data structure fits

List-এ index দিয়ে যেকোনো position O(1)-তে read/write করা যায়, তাই দুই প্রান্তের character swap করা মুহূর্তের কাজ। array-র এই random access-ই in-place swap সম্ভব করে — linked list হলে শেষ element-এ পৌঁছাতেই O(n) লাগত। তাই এখানে array নিখুঁতভাবে খাপ খায়।

6. Real-life analogy

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

7. Visual explanation

left ও right ভেতরের দিকে এগোয়, প্রতি step-এ একটা swap। ['a','b','c','d']:

call helper(0, 3):  ['a','b','c','d']   swap a,d -> ['d','b','c','a']
  └ call helper(1, 2): ['d','b','c','a'] swap b,c -> ['d','c','b','a']
      └ call helper(2, 1): left >= right -> base case, কিছু করো না, return

recursion ফিরে আসে, list এখন: ['d','c','b','a']
গভীরতা ≈ n/2 (প্রতি call দুটো প্রান্ত fix করে)

8. Example input and 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 (খালি): []      -> Output: []
Edge case 2 (একটা char): ['z'] -> Output: ['z']

9. Brute force thinking

প্রথম সরল চিন্তা: একটা নতুন list বানাও আর input-কে শেষ থেকে শুরুর দিকে পড়ে তাতে ঢালো।

out = []
for i = len(s)-1 down to 0:
    out.append(s[i])
return out

10. Why brute force is slow

কাজ করে, কিন্তু এটা O(n) extra space নেয় (নতুন list)। অথচ problem চায় in-place, O(1) extra space। তাছাড়া নতুন list বানিয়ে পুরোনোটা বদলানো অপ্রয়োজনীয় — দুই প্রান্তের swap দিয়েই কাজ হয়ে যায়, বাড়তি memory ছাড়াই।

11. Key observation

মূল observation: পুরো string একসাথে উল্টানোর দরকার নেই — শুধু symmetric জোড়াগুলো (i আর n-1-i) swap করলেই হয়, আর তা করতে হবে শুধু মাঝখান পর্যন্ত। বাকি অর্ধেক swap-গুলো প্রথম অর্ধেকের পুনরাবৃত্তি হবে, তাই left >= right-এ থামাই যথেষ্ট।

12. Optimized intuition

দুটো index নাও — left = 0, right = n-1। ওদের swap করো, তারপর left+1, right-1 দিয়ে recurse করো। যতক্ষণ left < right, ততক্ষণ একটা করে জোড়া fix হচ্ছে; left >= right হলে base case — থামো। চাইলে loop দিয়েও একই কাজ O(1) space-এ হয়, কিন্তু recursive version-টা decrease-and-conquer-এর "দুই প্রান্ত থেকে ছোট করা" রূপটা সুন্দরভাবে দেখায়।

13. Thinking tweak

মোচড়: "string উল্টাব" ভাবার বদলে ভাবো "বাইরের জোড়াটা swap করব, তারপর ভেতরের ছোট string-টা উল্টানোর দায়িত্ব recursion-কে দিয়ে দেব।" বড় কাজটা একটা swap + একটা ছোট, একই ধরনের কাজে ভেঙে যায় — leap of faith।

14. Step-by-step dry run

Input ['c','a','t','s'], helper(left, right):

  1. helper(0, 3): left=0 < right=3 → swap s[0],s[3] → ['s','a','t','c']; recurse helper(1,2)।
  2. helper(1, 2): left=1 < right=2 → swap s[1],s[2] → ['s','t','a','c']; recurse helper(2,1)।
  3. helper(2, 1): left=2 >= right=1 → base case, কিছু করো না, return।
  4. recursion unwind করে; final list = ['s','t','a','c']।

15. Python solution

def reverse_string(s):
    def helper(left, right):
        if left >= right:          # base case: জোড়া শেষ
            return
        s[left], s[right] = s[right], s[left]   # বাইরের জোড়া swap
        helper(left + 1, right - 1)             # ভেতরের দিকে recurse
    helper(0, len(s) - 1)
    return s                       # in-place, তবু সুবিধার জন্য return

# ---- 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([]) == []          # খালি list
assert reverse_string(["z"]) == ["z"]    # একটা char

# in-place হচ্ছে কি না যাচাই (একই object বদলাচ্ছে)
arr = ["c", "a", "t", "s"]
reverse_string(arr)
assert arr == ["s", "t", "a", "c"]
print("সব test pass!")

16. Line-by-line code explanation

  • def helper(left, right) — দুই প্রান্তের index নিয়ে কাজ করা ভেতরের recursive function।
  • if left >= right: return — base case: দুই pointer মিলে গেলে বা পেরিয়ে গেলে আর swap-এর কিছু নেই।
  • s[left], s[right] = s[right], s[left] — Python tuple-swap; বাইরের জোড়া এক লাইনে অদলবদল।
  • helper(left + 1, right - 1) — দুই দিক থেকে এক ঘর ভেতরে; problem ছোট হলো।
  • helper(0, len(s) - 1) — পুরো range দিয়ে শুরু।
  • return s — in-place বদলালেও test-এর সুবিধার জন্য list-টা ফেরত।

17. Output walkthrough

reverse_string(["h","e","l","l","o"]): helper(0,4) swap h,o; helper(1,3) swap e,l; helper(2,2) base case → ["o","l","l","e","h"]। palindrome-জাতীয় Hannah শুধু H↔h বদলায়। খালি ও single-char case base case-এ সরাসরি থামে। শেষ block প্রমাণ করে একই arr object in-place বদলেছে, তারপর print: সব test pass!।

18. Time complexity

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

19. Space complexity

O(n) recursion stack-এর জন্য (গভীরতা n/2)। Loop দিয়ে লিখলে O(1); in-place হওয়ায় কোনো নতুন list বানে না।

20. Common mistakes

  • base case left >= right-এর বদলে left == right লেখা — জোড় length-এ pointer পরস্পরকে cross করে যায়, তখন থামে না বা ভুল swap হয়।
  • in-place না করে নতুন list return করা — problem-এর শর্ত ভাঙে।
  • left+1, right-1 ভুলে left, right-1 বা উল্টোটা করা — infinite recursion বা ভুল ফল।
  • Python-এ গভীর recursion (খুব বড় list) — depth limit; তখন loop version বেছে নাও।

21. Which basic problem this inherits from

ভিত্তি: দুটো element swap + two-pointer ভেতরের দিকে হাঁটা। ../concept.md-এর "Decrease-and-conquer: string reverse" snippet (rev(s[1:]) + s[0]) দেখো — সেটা one-end shrink, এই note two-end swap, একই pattern-এর দুটো রূপ।

22. Similar harder problems

23. Pattern learned

Two-end decrease-and-conquer: বাইরের জোড়া swap করো, তারপর left+1, right-1 দিয়ে ভেতরের ছোট অংশের দায়িত্ব recursion-কে দাও — in-place reversal/palindrome-জাতীয় কাজের মূল pattern।

24. Final summary

ভবিষ্যতের আমাকে: "Reverse = বাইরের জোড়া swap করে ভেতরের দিকে recurse, left >= right-এ থামো।" যখনই কোনো problem-এ দুই প্রান্ত থেকে কাজ করে মাঝখানে মিলিয়ে দিতে হয় (reverse, palindrome check) — এই two-pointer / two-end pattern মনে করবে।

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