Problem link ও উৎস
- **Original source:** Classic stack-simulation exercise
- **Platform:** LeetCode —
- **Topic:** stack
- **Difficulty:** Easy
- **Pattern:** stack simulation
- **Basic idea inherited from:** matching / undo (problem 1) — `#` মানে শেষ character undo করা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে দুটো string `s` আর `t` দেওয়া আছে, যেন কেউ একটা text editor-এ এগুলো type করেছে। এখানে `#` মানে **backspace** — মানে আগের একটা character মুছে দাও। দুটো string টাইপ করা শেষ হলে যে final text পাওয়া যায়, সে দুটো এক হলে `True`, নাহলে `False` return করো।
মনে রেখো: খালি text-এ backspace চাপলে কিছুই হয় না (মোছার মতো কিছু নেই)।
### Input ও output {#8-example-input-and-output}
```text
Input : s="ab#c", t="ad#c" -> Output: True (দুটোই "ac")
Input : s="ab##", t="c#d#" -> Output: True (দুটোই "")
Input : s="a#c", t="b" -> Output: False ("c" vs "b")
Edge case (খালি-stack backspace): s="a##c", t="#a#c" -> True (দুটোই "c")
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
মোবাইলে message টাইপ করা ভাবো। অক্ষর চাপলে শেষে যোগ হয়; backspace চাপলে শেষ অক্ষরটা মুছে যায় — আগেরটা নয়, মাঝেরটা নয়, সবসময় *শেষটা*। আর input box খালি থাকলে backspace চাপলে কিছুই হয় না। এই "শেষে যোগ, শেষ থেকে মোছা" আচরণটাই stack।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা problem 1 (Valid Parentheses)-এর **undo discipline**-এর সরাসরি বংশধর। সেখানে closing bracket একটা খোলা context কে "শেষ" করত (pop); এখানে `#` শেষ typed character-টা "undo" করে (pop)। দুটোতেই key হলো: সবচেয়ে recent জিনিসটাই প্রথমে মুছে যায় — LIFO।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic হলো **একটা character-এর চূড়ান্ত ভাগ্য তার ডানদিকের `#`-গুলোর উপর নির্ভর করে।** তুমি যদি বাঁ থেকে ডানে process করো, একটা stack-এ চিন্তা সহজ: সাধারণ character push হয়, `#` সবচেয়ে recent push-টা pop করে। শেষে stack-এ যা থাকে সেটাই আসল text। invariant: যেকোনো মুহূর্তে stack = "এখন পর্যন্ত টাইপ করা, যা এখনো মোছা হয়নি।"
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
প্রতিটা string-এর জন্য একটা **stack** (Python `list`)। দুটো string-এর final stack বানিয়ে সরাসরি তুলনা করি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`#` মানে "শেষ typed character মুছে দাও" — ঠিক stack-এর `pop`, O(1)। সাধারণ character "শেষে যোগ করো" — `append`, O(1)। array-র মাঝখানে delete করতে গেলে O(n) shift লাগত; stack ঠিক যে প্রান্তটা দরকার (শেষ) সেটাই cheap রাখে, তাই নিখুঁত fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা `#` পেলে string-টা আক্ষরিকভাবে কেটে ছোট করি।
```text
"ab#c": '#'-এ পৌঁছে আগের char 'b' আর '#' নিজে — দুটোই মুছে -> "ac"
প্রতিবার '#' পেলে string slice করে নতুন বানাও।
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার `#`-এ string-টা slice/rebuild করলে প্রতিটা rebuild O(n), আর অনেকগুলো `#` থাকলে → **O(n^2)**। stack-ভিত্তিক approach পুরো string-এ একবার হাঁটে, প্রতিটা character-এ O(1) কাজ — মোট O(n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **`#` সবসময় সবচেয়ে recent টিকে-থাকা character-কে মোছে।** "সবচেয়ে recent টিকে-থাকা"-টা ঠিক stack-এর top। তাই একবার বাঁ-থেকে-ডানে scan করে stack maintain করলেই final text বেরিয়ে আসে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
প্রতিটা string-এর জন্য একটা helper লেখো যেটা string-এ হাঁটে: সাধারণ character হলে `append`, `#` হলে (stack খালি না হলে) `pop`। helper দুটো string-এর final stack ফেরত দেয়; সেই দুটো list সমান কিনা দেখো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "দুটো string তুলনা করব" — সরাসরি না ভেবে, আগে **প্রতিটাকে তার আসল রূপে evaluate করো** (backspace গুলো প্রয়োগ করে), তারপর তুলনা করো। evaluation-এর হাতিয়ারই হলো stack।
### ছবিতে বোঝা {#7-visual-explanation}
`"ab#c"` কীভাবে `"ac"` হয়, stack দিয়ে দেখি:
```text
char action stack (top ডানে)
'a' normal -> push [a]
'b' normal -> push [a, b]
'#' backspace -> pop শেষ (b) [a]
'c' normal -> push [a, c]
result = "ac"
```
খালি stack-এ backspace — `"#a#c"`:
```text
'#' backspace কিন্তু stack খালি -> কিছু হয় না []
'a' push [a]
'#' pop a []
'c' push [c]
result = "c"
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `s="ab##"`, `t="c#d#"`:
`build("ab##")`:
1. `'a'` → push → `[a]`
2. `'b'` → push → `[a, b]`
3. `'#'` → pop → `[a]`
4. `'#'` → pop → `[]` → result `[]`
`build("c#d#")`:
1. `'c'` → push → `[c]`
2. `'#'` → pop → `[]`
3. `'d'` → push → `[d]`
4. `'#'` → pop → `[]` → result `[]`
দুটো result সমান (`[] == []`) → return `True`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def backspace_compare(s, t):
def build(string):
stack = []
for ch in string:
if ch == '#':
if stack: # খালি না হলেই মোছো
stack.pop()
else:
stack.append(ch)
return stack
return build(s) == build(t)
# ---- tests ----
assert backspace_compare("ab#c", "ad#c") is True # দুটোই "ac"
assert backspace_compare("ab##", "c#d#") is True # দুটোই ""
assert backspace_compare("a#c", "b") is False # "c" vs "b"
assert backspace_compare("a##c", "#a#c") is True # দুটোই "c"
assert backspace_compare("xywrrmp", "xywrrmu#p") is True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `def build(string):` — একটা string-কে তার final (backspace-প্রয়োগ-করা) রূপে রূপান্তর করে।
- `if ch == '#':` — backspace হলে শেষ character মোছার চেষ্টা।
- `if stack:` — তবে stack খালি হলে কিছু করা যাবে না (খালি text-এ backspace = no-op)।
- `stack.pop()` — সবচেয়ে recent character মুছে ফেলো।
- `else: stack.append(ch)` — সাধারণ character শেষে যোগ করো।
- `return build(s) == build(t)` — দুটো final list সমান হলেই `True`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`backspace_compare("ab##", "c#d#")` → section 14-এর মতো দুটোই খালি `[]` → `True`। `backspace_compare("a#c", "b")` → `build("a#c")` = `['c']`, `build("b")` = `['b']`, সমান নয় → `False`। সব assert pass হয়ে শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n + m)** — `s`-এ n character, `t`-এ m character; প্রতিটা ঠিক একবার push/pop হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n + m)** — দুটো stack, সবচেয়ে খারাপ ক্ষেত্রে (কোনো `#` নেই) পুরো string জমে। (চাইলে two-pointer দিয়ে পিছন থেকে scan করে O(1) space-এ নামানো যায় — harder variant।)
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- খালি stack-এ `pop` করা — `#` পেলে আগে `if stack:` check না করলে error বা ভুল ফল।
- backspace-এর সময় শুধু `#`-টা মুছে আগের character না মোছা (বা উল্টোটা) — দুটোই বাদ যাওয়ার কথা; stack approach-এ একটা `pop`-ই দুটো সামলায়।
- দুটো string আলাদা দৈর্ঘ্যের বলে সাথে সাথে `False` ভাবা — backspace-এর পর final length এক হতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: problem 1 (Valid Parentheses)-এর undo/pop discipline; chapter-এর [../patterns.md](../patterns.md)-এর Pattern 1 (Matching / Nesting / Undo)। সেখানে "closing event pop করে", এখানে "`#` pop করে" — একই কঙ্কাল।
### পরের অনুশীলন {#22-similar-harder-problems}
- Backspace String Compare-এর O(1)-space (two-pointer) সংস্করণ — একই official link, follow-up: