010 — Decode String

Source

• Original source: Classic nested-stack exercise
• Platform: LeetCode — https://leetcode.com/problems/decode-string/
• 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/)

1. Problem in simple words

তোমাকে একটা encoded string দেওয়া আছে যার নিয়ম: k[content] মানে ভেতরের content-টা k বার পরপর বসবে। এই [...] আবার ভেতরে আরেকটা [...] ধরে রাখতে পারে (nested)। তোমাকে পুরোটা খুলে আসল string বের করতে হবে।

"3[a]2[bc]"   -> "aaabcbc"
"3[a2[c]]"    -> "accaccacc"      (ভেতরের 2[c]=cc, তারপর a+cc=acc, তারপর 3 বার)
"2[abc]3[cd]ef" -> "abcabccdcdcdef"

2. Which basic idea does this inherit from?

এটা Problem 1 (Valid Parentheses)-এর nesting idea-র উপর দাঁড়িয়ে। সেখানে [ খুললে আর ] বন্ধ করলে; এখানেও ঠিক তাই, কিন্তু bracket শুধু match করেই থেমে থাকে না — প্রতিটা [-এর সাথে আমরা একটা পুরো context (আগের লেখা string আর repeat count) সঞ্চয় করি, আর ]-এ সেটা ফিরিয়ে এনে গুণ করি। সাথে যোগ হয় ../../02-arrays-and-strings/-এর সাধারণ 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)।

6. Real-life analogy

ভাবো তুমি একটা বইয়ের ভেতরে footnote পড়তে গিয়ে আরেকটা footnote-এ ঢুকে পড়লে, সেটার ভেতরে আবার আরেকটা। প্রতিবার ভেতরে ঢোকার আগে তুমি bookmark রাখো — "মূল লেখায় ঠিক এখানে ফিরব"। সবচেয়ে ভেতরের footnote শেষ করে তুমি শেষ bookmark-টা তুলে আগের জায়গায় ফেরো, তারপর তার আগেরটায়। stack ঠিক এই bookmark-গুলোর গাদা — শেষে-রাখা bookmark আগে তোলা হয়।

7. Visual explanation

"3[a2[c]]" কীভাবে খোলে, দেখি (top ডানে):

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"

8. Example input and output

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"

9. Brute force thinking

সরল চিন্তা: সবচেয়ে ভেতরের k[...] (যেটায় ভেতরে আর কোনো bracket নেই) খুঁজে বের করে তাকে expand করো, string-টা নতুন করে লেখো, আবার ভেতরের একটা খুঁজে expand করো — যতক্ষণ আর কোনো bracket না থাকে।

"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 একই থাকে।

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"

15. Python solution

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-এ যোগ।

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!।

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 নয়; বাইরের অংশ আগে বসে।

21. Which basic problem this inherits from

ভিত্তি: Problem 1-এর matching/nesting discipline। chapter-এর ../patterns.md-এর Pattern 1 (Matching / Nesting / Undo) এখানে context save/restore রূপে; string building-এর অংশটা ../../02-arrays-and-strings/ থেকে আসে।

22. Similar harder problems

• Basic Calculator (parentheses-এ context save/restore) — https://leetcode.com/problems/basic-calculator/ (এই tracker-এর #22)
• Number of Atoms (nested formula parse) — https://leetcode.com/problems/number-of-atoms/
• Brace Expansion II — https://leetcode.com/problems/brace-expansion-ii/

23. Pattern learned

Stack of contexts: nesting (k[...], parentheses) দেখলে প্রতিটা open-এ চলতি context push করো, প্রতিটা close-এ pop করে ভেতরের ফলটা বাইরের সাথে মিলিয়ে দাও — "decode", "nested", "expand" এই trigger।

24. Final summary

ভবিষ্যতের আমাকে: [-এ (count, আগের string) push করে reset, ]-এ pop করে prev + current*count। multi-digit-এর জন্য num*10+অঙ্ক মনে রেখো। "nested", "decode", "k[...]" দেখলেই দুটো stack-এর context save/restore ভাববে।

---

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