Problem link ও উৎস
- **Original source:** Classic stack-based string-building exercise
- **Platform:** LeetCode —
- **Topic:** string / stack
- **Difficulty:** Medium
- **Pattern:** string building + stack (nested repeat খুলে আনা)
- **Basic idea inherited from:** string building (fragment list + join); [../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-এর stack pattern-এর preview
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা encoded string দেওয়া, যেখানে নিয়ম: `k[content]` মানে ভেতরের `content`-টা `k` বার পরপর বসবে। এগুলো নেস্টেডও হতে পারে — যেমন `3[a2[c]]`। তোমাকে পুরোটা **decode** করে আসল string বানিয়ে দিতে হবে। সংখ্যা `k` সবসময় ধনাত্মক, আর bracket সবসময় balanced।
```text
"3[a]2[bc]" -> "aaabcbc"
"3[a2[c]]" -> "accaccacc" (ভেতরের 2[c]=cc, তারপর a+cc=acc, বাইরে x3)
```
### Input ও output {#8-example-input-and-output}
```text
Input : "3[a]2[bc]" -> "aaabcbc"
Input : "3[a2[c]]" -> "accaccacc"
Input : "2[abc]3[cd]ef" -> "abcabccdcdcdef"
Edge case (multi-digit count): "10[a]" -> "aaaaaaaaaa" (10টা a)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একটা চিঠি লিখছ, হঠাৎ ভেতরে একটা উদ্ধৃতি (quote) আসবে যেটা আবার নিজে কয়েকবার repeat হবে। তুমি মূল চিঠিটা পাশে সরিয়ে রাখো (push), উদ্ধৃতিটা আগে পুরো লিখে কয়েকবার copy করো, তারপর মূল চিঠি ফেরত এনে (pop) সেই copy-গুলো জুড়ে দাও। ভেতরের কাজ শেষ না করে বাইরেরটায় ফেরো না — এটাই stack।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত: (১) **string building** — উত্তরটা টুকরো টুকরো করে বানাই, আর immutable string বারবার না বাড়িয়ে fragment একটা list-এ জমিয়ে শেষে `join` করি ([../patterns.md](../patterns.md)-এর "Pattern 6 — String Building")। (২) **stack** — nested bracket খুলতে গেলে "বাইরের কাজটা একটু থামিয়ে রাখো, ভেতরেরটা আগে শেষ করো" দরকার, এটাই stack-এর LIFO স্বভাব। এটা [../../04-stack-and-queue/](../../04-stack-and-queue/README.md)-এর একটা ভদ্র preview।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: bracket-গুলো একটা **recursive / nested গঠন** তৈরি করে — ঠিক যেমন গাণিতিক expression-এ বন্ধনী। প্রতিটা `[` মানে "নতুন একটা ভেতরের স্তরে নামছি", আর `]` মানে "এই স্তর শেষ, এর ফলটা `k` বার নিয়ে বাইরের স্তরে যোগ করো।" stack ঠিক এই স্তরে-স্তরে ওঠা-নামাটাকে মনে রাখে: যখন `[` দেখি তখন বাইরের (অসম্পূর্ণ) অবস্থা push করি, `]`-এ pop করে মিলিয়ে দিই।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **stack**, যার প্রতিটা entry এক জোড়া: (ওই স্তরে এ পর্যন্ত বানানো fragment-list, ওই স্তরের repeat count `k`)। সাথে চলতি স্তরের জন্য একটা fragment-list `current` আর একটা চলমান সংখ্যা `num` (multi-digit count বানাতে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
nested বন্ধনীতে **শেষে-খোলাটা আগে-বন্ধ হয়** (last-opened, first-closed) — এটাই hubu LIFO, stack-এর জন্মগত স্বভাব। `[` দেখলে বাইরের কাজ push করে রেখে ভেতরে নামি, `]` দেখলে pop করে ভেতরের ফলটা বাইরের সাথে মেলাই। আর fragment list + `join` ব্যবহারে string-কে বারবার copy করার O(n^2) ফাঁদ এড়াই (Pattern 6)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: recursion দিয়ে — সবচেয়ে ভেতরের `k[...]` খুঁজে সেটা expand করো, string-এ বসাও, তারপর আবার পুরো string scan করে পরের ভেতরের bracket খোঁজো; bracket শেষ না হওয়া পর্যন্ত repeat।
```text
while string-এ '[' আছে:
সবচেয়ে ভেতরের k[content] খোঁজো (যার ভিতরে আর '[' নেই)
সেটাকে content*k দিয়ে replace করো
return string
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার পুরো string আবার scan + নতুন string বানানো — অনেকগুলো bracket থাকলে বহুবার পুরোটা copy হয়, সহজেই **O(n^2)** বা বাজে। তাছাড়া বারবার "সবচেয়ে ভেতরের bracket" খোঁজা ব্যয়বহুল। stack দিয়ে একবার বাঁ-থেকে-ডান scan-এই (single pass) সব স্তর সামলানো যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: এটা একটা **single left-to-right pass**-এই হয় যদি তুমি স্তর-গুলোর অসম্পূর্ণ অবস্থা stack-এ রাখো। `]`-এ পৌঁছালে শুধু সবচেয়ে ভেতরের (top-of-stack) স্তরটাই "সম্পূর্ণ" — তাকে `k` বার নিয়ে এক স্তর বাইরে জুড়ে দাও। পুরো string বারবার পড়ার দরকার নেই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
বাঁ থেকে ডানে এক-এক character পড়ো:
- digit হলে `num = num*10 + int(ch)` (multi-digit count বানাতে)।
- `[` হলে এখনকার `(current, num)` push করো, তারপর `current` খালি ও `num=0` রিসেট করো (নতুন ভেতরের স্তর)।
- `]` হলে `(prev, k)` pop করো; `current = prev + current * k` (ভেতরের ফল k বার নিয়ে বাইরের সাথে জোড়া)।
- সাধারণ অক্ষর হলে `current`-এ append।
শেষে `"".join(current)`। সব কাজ এক pass, output-এর আকারের সমানুপাতিক।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "বারবার পুরো string-এ ভেতরের bracket খুঁজে replace করব" ভোলো। বরং ভাবো "এক pass-এ হাঁটি; `[` মানে current অবস্থা পকেটে (stack-এ) রাখি, `]` মানে পকেট থেকে বের করে ভেতরের ফল মিলিয়ে দিই।" আর string না বাড়িয়ে fragment list-এ জমিয়ে শেষে একবার join করি।
### ছবিতে বোঝা {#7-visual-explanation}
`"3[a2[c]]"` decode — stack-এ স্তর ওঠানামা:
```text
'3' num=3
'[' push (current=[], k=3); current=[] stack: [([],3)]
'a' current=['a']
'2' num=2
'[' push (current=['a'], k=2); current=[] stack: [([],3), (['a'],2)]
'c' current=['c']
']' pop (['a'],2) -> current = ['a'] + ['c']*2 = ['a','c','c']
']' pop ([],3) -> current = [] + ['a','c','c']*3
= ['a','c','c','a','c','c','a','c','c']
join -> "accaccacc"
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `"3[a]2[bc]"`:
1. `'3'` → `num=3`।
2. `'['` → push `([], 3)`; `current=[]`, `num=0`।
3. `'a'` → `current=['a']`।
4. `']'` → pop `([],3)` → `current = [] + ['a']*3 = ['a','a','a']`।
5. `'2'` → `num=2`।
6. `'['` → push `(['a','a','a'], 2)`; `current=[]`, `num=0`।
7. `'b','c'` → `current=['b','c']`।
8. `']'` → pop `(['a','a','a'],2)` → `current = ['a','a','a'] + ['b','c']*2 = ['a','a','a','b','c','b','c']`।
9. `"".join(current)` → `"aaabcbc"`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def decode_string(s):
stack = [] # (বাইরের fragment-list, repeat count k)
current = [] # এই স্তরের fragment-গুলো (list, এখনই join নয়)
num = 0 # multi-digit count জমানোর জন্য
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '[':
stack.append((current, num)) # বাইরের অবস্থা থামিয়ে রাখি
current = []
num = 0
elif ch == ']':
prev, k = stack.pop()
current = prev + current * k # ভেতরের ফল k বার, বাইরের সাথে জোড়া
else:
current.append(ch)
return "".join(current) # শেষে একবার join (O(n^2) এড়াই)
# ---- 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("10[a]") == "a" * 10 # multi-digit count
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `stack = []` — প্রতিটা খোলা bracket-স্তরের অসম্পূর্ণ অবস্থা এখানে থাকে।
- `current = []` — চলতি স্তরে এ পর্যন্ত বানানো fragment-গুলো; list বলে append সস্তা।
- `num = 0` — সংখ্যা একসাথে কয়েক digit হতে পারে, তাই জমিয়ে রাখি।
- `if ch.isdigit(): num = num*10 + int(ch)` — `"10"` দেখলে 1 → 10 হয়।
- `elif ch == '[':` — বাইরের `(current, num)` push, তারপর ভেতরের স্তরের জন্য reset।
- `elif ch == ']':` — top pop করে `prev + current * k`; list-এ `* k` মানে list-টা k বার repeat, `+` মানে concat।
- `else: current.append(ch)` — সাধারণ অক্ষর সরাসরি যোগ।
- `return "".join(current)` — Pattern 6: সব fragment শেষে একবারে জোড়া, প্রতিটা অক্ষর ঠিক একবার লেখা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"3[a]2[bc]"` → `aaa` + `bcbc` = `"aaabcbc"`, assert pass। `"3[a2[c]]"` → ভেতরের `2[c]=cc`, `a+cc=acc`, বাইরে x3 = `"accaccacc"`; `"2[abc]3[cd]ef"` → `abcabc`+`cdcdcd`+`ef` = `"abcabccdcdcdef"`; `"10[a]"` → 10টা `a`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(N)** — N = decode করার পরের output-এর দৈর্ঘ্য; প্রতিটা output-character ঠিক একবার তৈরি/copy হয় (fragment list + শেষ join), input একবার scan।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(N)** — output রাখার জায়গা, আর nesting-এর গভীরতা অনুযায়ী stack (worst case nesting-সংখ্যার সমানুপাতিক)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- single-digit ধরে নেওয়া (`num = int(ch)`) — `"10[a]"`-এর মতো multi-digit count ভেঙে যায়; `num*10 + ...` লাগে।
- `[`-এ `num` reset না করা বা `current` reset না করা — পরের স্তরে আগের আবর্জনা মিশে যায়।
- `current`-কে string ধরে `current += ch` করা loop-এ — immutable string বারবার copy হয়ে O(n^2) (Pattern 6-এর ঠিক যে ফাঁদ); তাই list + join।
- `]`-এ `prev + current*k`-এর বদলে `current*k + prev` লেখা — ক্রম উল্টে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: string building (fragment list + join, Pattern 6) + stack-এর LIFO। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 6 — String Building" দেখো; আর stack-এর পূর্ণ গল্প [../../04-stack-and-queue/patterns.md](../../04-stack-and-queue/patterns.md)-তে — এই problem সেখানকার "matching / nested structure" pattern-এর একটা সুন্দর introduction।
### পরের অনুশীলন {#22-similar-harder-problems}
- Valid Parentheses (নিখাদ stack matching) —