Problem link ও উৎস
- **Original source:** Classic nested-stack exercise
- **Platform:** LeetCode —
- **Topic:** stack (nesting / stack of contexts)
- **Difficulty:** Medium
- **Pattern:** nesting — stack of contexts
- **Basic idea inherited from:** Problem 1 (matching / nesting) + string building ([../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা encoded string দেওয়া আছে যার নিয়ম: `k[content]` মানে ভেতরের `content`-টা `k` বার পরপর বসবে। এই `[...]` আবার ভেতরে আরেকটা `[...]` ধরে রাখতে পারে (nested)। তোমাকে পুরোটা খুলে আসল string বের করতে হবে।
```text
"3[a]2[bc]" -> "aaabcbc"
"3[a2[c]]" -> "accaccacc" (ভেতরের 2[c]=cc, তারপর a+cc=acc, তারপর 3 বার)
"2[abc]3[cd]ef" -> "abcabccdcdcdef"
```
### Input ও output {#8-example-input-and-output}
```text
Input : "3[a]2[bc]" -> Output: "aaabcbc"
Input : "3[a2[c]]" -> Output: "accaccacc"
Input : "2[abc]3[cd]ef"-> Output: "abcabccdcdcdef"
Edge case 1 (bracket নেই) : "abc" -> "abc"
Edge case 2 (multi-digit k) : "10[a]" -> "aaaaaaaaaa" (k দুই অঙ্কের, 10)
Edge case 3 (গভীর nesting) : "2[2[b]]" -> "bbbb"
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা বইয়ের ভেতরে footnote পড়তে গিয়ে আরেকটা footnote-এ ঢুকে পড়লে, সেটার ভেতরে আবার আরেকটা। প্রতিবার ভেতরে ঢোকার আগে তুমি bookmark রাখো — "মূল লেখায় ঠিক এখানে ফিরব"। সবচেয়ে ভেতরের footnote শেষ করে তুমি শেষ bookmark-টা তুলে আগের জায়গায় ফেরো, তারপর তার আগেরটায়। stack ঠিক এই bookmark-গুলোর গাদা — শেষে-রাখা bookmark আগে তোলা হয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা **Problem 1 (Valid Parentheses)**-এর nesting idea-র উপর দাঁড়িয়ে। সেখানে `[` খুললে আর `]` বন্ধ করলে; এখানেও ঠিক তাই, কিন্তু bracket শুধু match করেই থেমে থাকে না — প্রতিটা `[`-এর সাথে আমরা একটা পুরো **context** (আগের লেখা string আর repeat count) সঞ্চয় করি, আর `]`-এ সেটা ফিরিয়ে এনে গুণ করি। সাথে যোগ হয় [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md)-এর সাধারণ string building।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **context save/restore**: প্রতিটা `[` একটা নতুন "ভেতরের জগৎ" শুরু করে। ভেতরে ঢোকার আগে আমরা বাইরের জগতের দুটো জিনিস stack-এ জমিয়ে রাখি — (1) এ পর্যন্ত বানানো বাইরের string, আর (2) এই block কতবার repeat হবে সেই সংখ্যা।
`]` এলে ভেতরের জগতের কাজ শেষ; আমরা count আর আগের string ফিরিয়ে এনে হিসাব করি: `current = আগের_string + current * count`। nesting যত গভীরই হোক, stack ঠিক ঠিক সবচেয়ে-ভেতরের context-টা top-এ রাখে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো **stack** — একটা `count_stack` (প্রতিটা `[`-এর repeat সংখ্যা), আরেকটা `string_stack` (প্রতিটা `[`-এর আগে বানানো বাইরের string)। সাথে দুটো চলতি variable: `current` (এই মুহূর্তে বানানো string) আর `num` (এই মুহূর্তে পড়া সংখ্যা, যা multi-digit হতে পারে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
nesting মানেই "সবচেয়ে ভেতরের block আগে শেষ হবে" — খাঁটি LIFO, তাই stack। আর প্রতিটা level-এ দুই টুকরো তথ্য (count + আগের string) মনে রাখতে হয় বলে দুটো parallel stack নিখুঁতভাবে খাপ খায়: `[`-এ দুটোতেই একসাথে push, `]`-এ দুটো থেকেই একসাথে pop। push/pop সব O(1)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: সবচেয়ে ভেতরের `k[...]` (যেটায় ভেতরে আর কোনো bracket নেই) খুঁজে বের করে তাকে expand করো, string-টা নতুন করে লেখো, আবার ভেতরের একটা খুঁজে expand করো — যতক্ষণ আর কোনো bracket না থাকে।
```text
"3[a2[c]]" -> ভেতরের 2[c] পাও -> "3[acc]" -> 3[acc] পাও -> "accaccacc"
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার একটা ভেতরের bracket খুঁজতে পুরো string scan করতে হয়, আর expand-এর পর string নতুন করে গড়তে হয়। অনেক nested level থাকলে এটা বহুবার repeat হয় → কমপক্ষে **O(n * depth)** scan, আর বারবার বড় string নতুন করে বানানোর খরচ আলাদা। একবার বাঁ-থেকে-ডানে hাঁটাতেই stack দিয়ে সব হয়ে যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: তুমি বাঁ থেকে ডানে একবার hাঁটলেই হয়, কারণ যে মুহূর্তে `]` দেখবে, সেই block-এর পুরো ভেতরটা ততক্ষণে `current`-এ তৈরি, আর তার count ও বাইরের string stack-এ অপেক্ষা করছে। অর্থাৎ "কোন context-এর ভেতরে আছি" প্রশ্নের exact উত্তর সবসময় stack-এর top।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একবার hাঁটো। digit হলে `num`-এ জমাও (`num = num*10 + অঙ্ক`, multi-digit সামলাতে)। `[` হলে `num` আর `current` দুই stack-এ push করে দুটোই reset করো। অক্ষর হলে `current`-এ যোগ করো। `]` হলে count আর আগের string pop করে `current = আগের + current * count` বানাও। শেষে `current`-ই উত্তর।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** `]` দেখাটাকে "bracket বন্ধ" না ভেবে ভাবো "একটা ভেতরের জগৎ সম্পূর্ণ হলো, এবার তাকে গুণ করে বাইরের জগতে গেঁথে দিই"। তখন repeat-করাটা একটা গুছিয়ে রাখা context-restore হয়ে যায়, আর nesting যত গভীরই হোক code একই থাকে।
### ছবিতে বোঝা {#7-visual-explanation}
`"3[a2[c]]"` কীভাবে খোলে, দেখি (top ডানে):
```text
ch action count_stack string_stack current num
3 digit [] [] "" 3
[ push context, reset [3] [""] "" 0
a current += 'a' [3] [""] "a" 0
2 digit [3] [""] "a" 2
[ push context, reset [3,2] ["","a"] "" 0
c current += 'c' [3,2] ["","a"] "c" 0
] pop: cur = "a" + "c"*2 = "acc" [3] [""] "acc" 0
] pop: cur = "" + "acc"*3 [] [] "accaccacc"
end return "accaccacc"
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `"3[a]2[bc]"`:
1. `3` — `num = 3`
2. `[` — push: `count_stack=[3]`, `string_stack=[""]`; reset `num=0`, `current=""`
3. `a` — `current = "a"`
4. `]` — pop `3` আর `""`; `current = "" + "a"*3 = "aaa"`
5. `2` — `num = 2`
6. `[` — push: `count_stack=[2]`, `string_stack=["aaa"]`; reset
7. `b`,`c` — `current = "bc"`
8. `]` — pop `2` আর `"aaa"`; `current = "aaa" + "bc"*2 = "aaabcbc"`
9. string শেষ → return `"aaabcbc"`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def decode_string(s):
count_stack = [] # প্রতিটা [-এর repeat সংখ্যা
string_stack = [] # প্রতিটা [-এর আগের বাইরের string
current = "" # এই মুহূর্তে বানানো string
num = 0 # এই মুহূর্তে পড়া সংখ্যা (multi-digit হতে পারে)
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch) # multi-digit সামলাও
elif ch == '[':
count_stack.append(num) # context save
string_stack.append(current)
num = 0
current = ""
elif ch == ']':
repeat = count_stack.pop() # context restore
prev = string_stack.pop()
current = prev + current * repeat
else:
current += ch # সাধারণ অক্ষর
return current
# ---- tests ----
assert decode_string("3[a]2[bc]") == "aaabcbc"
assert decode_string("3[a2[c]]") == "accaccacc"
assert decode_string("2[abc]3[cd]ef") == "abcabccdcdcdef"
assert decode_string("abc") == "abc" # bracket নেই
assert decode_string("10[a]") == "a" * 10 # multi-digit k
assert decode_string("2[2[b]]") == "bbbb" # গভীর nesting
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `count_stack`, `string_stack` — দুটো parallel stack; `[`-এ একসাথে push, `]`-এ একসাথে pop।
- `current`, `num` — চলতি অবস্থা: এ পর্যন্ত বানানো string আর এ পর্যন্ত পড়া সংখ্যা।
- `if ch.isdigit(): num = num*10 + int(ch)` — দুই বা তিন অঙ্কের সংখ্যা সঠিকভাবে গড়ে তোলে।
- `elif ch == '[':` — নতুন ভেতরের জগৎ; বাইরের count আর string জমিয়ে রেখে দুটো reset করো।
- `elif ch == ']':` — ভেতরের জগৎ শেষ; `current = prev + current * repeat` দিয়ে গুণ করে বাইরের জগতে গেঁথে দাও।
- `else: current += ch` — সাধারণ অক্ষর হলে চলতি string-এ যোগ।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`decode_string("3[a2[c]]")` → section 7-এর trace মতো ভেতরের `2[c]` আগে `"cc"`, তারপর `"acc"`, শেষে `"accaccacc"`। `decode_string("10[a]")` → `num` দুই অঙ্ক মিলে `10`, তাই দশটা `a`। সব assert pass করে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n + output length)** — input-এর প্রতিটা character একবার পড়া হয়, আর সবচেয়ে বড় খরচ আসে আসল decoded string-টা গড়তে, যার দৈর্ঘ্যই hisaব-এ আসে।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n + output length)** — stack-এর গভীরতা nesting-এর সমান (সবচেয়ে খারাপ O(n)), আর `current` ক্রমে decoded string-এর সমান বড় হয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- single-digit ধরে নেওয়া — `num = int(ch)` লিখলে `10[a]` ভেঙে যায়; `num*10 + অঙ্ক` লাগে।
- `[`-এ `current` reset না করা — তাহলে বাইরের অক্ষর ভেতরের block-এ মিশে যায়।
- count আর string stack-এর order উল্টে ফেলা — `current = prev + current*repeat`, `current*repeat + prev` নয়; বাইরের অংশ আগে বসে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: Problem 1-এর matching/nesting discipline। chapter-এর [../patterns.md](../patterns.md)-এর Pattern 1 (Matching / Nesting / Undo) এখানে context save/restore রূপে; string building-এর অংশটা [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md) থেকে আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Basic Calculator (parentheses-এ context save/restore) —