Skip to content

019 — Decode String

Source

  • Original source: Classic stack-based string-building exercise
  • Platform: LeetCode — https://leetcode.com/problems/decode-string/
  • Topic: string / stack
  • Difficulty: Medium
  • Pattern: string building + stack (nested repeat খুলে আনা)
  • Basic idea inherited from: string building (fragment list + join); ../../04-stack-and-queue/-এর stack pattern-এর preview

1. Problem in simple words

একটা encoded string দেওয়া, যেখানে নিয়ম: k[content] মানে ভেতরের content-টা k বার পরপর বসবে। এগুলো নেস্টেডও হতে পারে — যেমন 3[a2[c]]। তোমাকে পুরোটা decode করে আসল string বানিয়ে দিতে হবে। সংখ্যা k সবসময় ধনাত্মক, আর bracket সবসময় balanced।

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

2. Which basic idea does this inherit from?

দুটো ভিত: (১) string building — উত্তরটা টুকরো টুকরো করে বানাই, আর immutable string বারবার না বাড়িয়ে fragment একটা list-এ জমিয়ে শেষে join করি (../patterns.md-এর "Pattern 6 — String Building")। (২) stack — nested bracket খুলতে গেলে "বাইরের কাজটা একটু থামিয়ে রাখো, ভেতরেরটা আগে শেষ করো" দরকার, এটাই stack-এর LIFO স্বভাব। এটা ../../04-stack-and-queue/-এর একটা ভদ্র 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)।

6. Real-life analogy

ভাবো তুমি একটা চিঠি লিখছ, হঠাৎ ভেতরে একটা উদ্ধৃতি (quote) আসবে যেটা আবার নিজে কয়েকবার repeat হবে। তুমি মূল চিঠিটা পাশে সরিয়ে রাখো (push), উদ্ধৃতিটা আগে পুরো লিখে কয়েকবার copy করো, তারপর মূল চিঠি ফেরত এনে (pop) সেই copy-গুলো জুড়ে দাও। ভেতরের কাজ শেষ না করে বাইরেরটায় ফেরো না — এটাই stack।

7. Visual explanation

"3[a2[c]]" decode — stack-এ স্তর ওঠানামা:

'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"

8. Example input and output

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)

9. Brute force thinking

প্রথম সরল চিন্তা: recursion দিয়ে — সবচেয়ে ভেতরের k[...] খুঁজে সেটা expand করো, string-এ বসাও, তারপর আবার পুরো string scan করে পরের ভেতরের bracket খোঁজো; bracket শেষ না হওয়া পর্যন্ত repeat।

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 করি।

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

15. Python solution

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 শেষে একবারে জোড়া, প্রতিটা অক্ষর ঠিক একবার লেখা।

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

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 লেখা — ক্রম উল্টে যায়।

21. Which basic problem this inherits from

ভিত্তি: string building (fragment list + join, Pattern 6) + stack-এর LIFO। chapter-এর ../patterns.md-এর "Pattern 6 — String Building" দেখো; আর stack-এর পূর্ণ গল্প ../../04-stack-and-queue/patterns.md-তে — এই problem সেখানকার "matching / nested structure" pattern-এর একটা সুন্দর introduction।

22. Similar harder problems

23. Pattern learned

Stack for nested structure + fragment-list building: "nested bracket / repeat খুলে আনো" দেখলে এক pass-এ হাঁটো, [-এ বাইরের অবস্থা push, ]-এ pop করে মিলাও; উত্তর string fragment list-এ জমিয়ে শেষে join — O(N), O(n^2) copy-ফাঁদ ছাড়া।

24. Final summary

ভবিষ্যতের আমাকে: "decode = এক pass; digit জমাও, [-এ push, ]-এ pop করে prev + cur*k, শেষে join।" "nested repeat / বন্ধনী খোলা" দেখলেই stack + fragment-list মনে করবে — single pass O(N), string বারবার বাড়ানো নয়।

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