Skip to content

021 — Substring with Concatenation of All Words

Source

  • Original source: Classic frequency-counting + fixed-window exercise
  • Platform: LeetCode — https://leetcode.com/problems/substring-with-concatenation-of-all-words/
  • Topic: hash map (word counts) + fixed-size sliding window
  • Difficulty: Hard
  • Pattern: frequency counting + fixed windows
  • Basic idea inherited from: Minimum Window Substring — count মেলানো, কিন্তু এখন অক্ষরের বদলে সমান-দৈর্ঘ্যের word, আর window-এর দৈর্ঘ্য স্থির

1. Problem in simple words

একটা string s আর সমান-দৈর্ঘ্যের কিছু word-এর তালিকা words দেওয়া আছে (word পুনরাবৃত্তও থাকতে পারে)। s-এর মধ্যে এমন সব শুরু-index খুঁজতে হবে যেখান থেকে শুরু করে words-এর প্রতিটা word ঠিক একবার, মাঝে কোনো ফাঁক ছাড়া, যেকোনো ক্রমে পরপর বসানো যায়।

s = "barfoothefoobarman", words = ["foo", "bar"]
index 0: "barfoo" = "bar" + "foo"  ✓
index 9: "foobar" = "foo" + "bar"  ✓
উত্তর: [0, 9]

2. Which basic idea does this inherit from?

এটা সরাসরি Minimum Window Substring (#20)-এর আত্মীয়, এক ধাপ এগিয়ে। ওখানে count ছিল অক্ষরের আর window-এর দৈর্ঘ্য পরিবর্তনশীল; এখানে count হলো word-এর (Pattern 1, frequency counting) আর প্রতিটা valid window-এর দৈর্ঘ্য স্থির (word_len × সংখ্যা)। তাই string-কে word-একক ধাপে হাঁটি, আর fixed-length window-এ word-count মেলাই।

3. What is the hidden math or logic?

লুকানো logic: সব word সমান-দৈর্ঘ্যের (L) হওয়ায় একটা valid block-এর মোট দৈর্ঘ্য সবসময় L × k (যেখানে k = len(words)) — fixed। আর যেহেতু block-গুলো L-এর গুণিতকে শুরু হয়, প্রতিটা সম্ভাব্য শুরু-position-এর "phase" হলো 0, 1, ..., L-1-এর কোনো একটা। তাই Lটা আলাদা সারিবদ্ধতা (offset) ধরে word-একক ধাপে sliding window চালালে প্রতিটা শুরু-position ঠিক একবার করে বিবেচিত হয় — কোনো position বাদ যায় না, পুনরাবৃত্তও হয় না।

4. Which data structure is needed?

দুটো hash map / Counter: need (word → কতবার লাগবে) আর window (এখনকার block-এ word → কতবার আছে)। সাথে কয়েকটা integer: word_len (L), num_words (k), আর প্রতি offset-এ left/count। word-গুলোকে key বানানো যায় কারণ string hashable।

5. Why this data structure fits

word পুনরাবৃত্ত থাকতে পারে (যেমন ["word","word","good"]), তাই set নয়, count চাই — Counter ঠিক তাই দেয়, আর অনুপস্থিত key-তে 0। প্রতিটা L-অক্ষর টুকরোকে এক ধাপে word হিসেবে slice করে need-এর সাথে মেলাই, count update/lookup গড়ে O(1)। ফলে প্রতিটা position-এ শূন্য থেকে না গুনে incremental window চালানো যায়।

6. Real-life analogy

ভাবো তোমার হাতে কয়েকটা নির্দিষ্ট রঙের লেগো ব্লক — 2টা লাল, 1টা নীল (এটাই need)। একটা লম্বা সারিতে সমান মাপের ব্লক বসানো; তুমি জানালা দিয়ে পরপর কয়েকটা ব্লক দেখছ, ঠিক ততগুলো যত হাতে আছে। জানালার ভেতরের রঙের হিসাব যদি হুবহু তোমার হাতের হিসাবের সমান হয় — পেয়ে গেছ এক জায়গা। জানালা এক-ব্লক ডানে সরাও: বাঁয়ের ব্লক বাদ, ডানে নতুন ব্লক যোগ — পুরো গোনা নতুন করে নয়।

7. Visual explanation

s = "barfoothefoobarman", words = ["foo","bar"]; L=3, k=2, need = {foo:1, bar:1}। offset 0-এ word-একক ধাপে হাঁটি:

right=0  "bar"  need-এ আছে  window{bar:1}              count=1
right=3  "foo"  need-এ আছে  window{bar:1,foo:1}        count=2 == k → index 0 ✓
right=6  "the"  need-এ নেই  → window রিসেট, count=0, left=9
right=9  "foo"  window{foo:1}                          count=1
right=12 "bar"  window{foo:1,bar:1}                    count=2 == k → index 9 ✓
right=15 "man"  need-এ নেই  → রিসেট
উত্তর (offset 0): [0, 9]

offset 1 ও 2-তে কোনো word সারিবদ্ধ হয় না, তাই নতুন index আসে না।

8. Example input and output

Input : s = "barfoothefoobarman", words = ["foo","bar"]               Output: [0, 9]
Input : s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]  Output: []
Input : s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]   Output: [6, 9, 12]
Input : s = "", words = ["a"]                                         Output: []

9. Brute force thinking

প্রথম সরল চিন্তা: s-এর প্রতিটা সম্ভাব্য শুরু-index ধরে total দৈর্ঘ্যের টুকরো কেটে নাও, সেটাকে L-অক্ষরে ভাগ করে word-গুলো বের করো, তারপর সেই word-গুলোর Counter need-এর সমান কি না দেখো।

total = L * k
প্রতিটা শুরু i (0 .. len(s)-total)-র জন্য:
    block = s[i : i+total]
    block-কে L-অক্ষরে ভেঙে word-গুলো বের করো
    সেই word-গুলোর Counter == need হলে i-কে উত্তরে রাখো

10. Why brute force is slow

প্রতিটা শুরু-index-এ আমরা পুরো block আবার L-অক্ষরে ভেঙে নতুন Counter বানাই — O(n · k), n শুরু-position আর প্রতিটায় k word। অপচয়টা Minimum Window Substring-এর মতোই: পাশাপাশি দুটো block-এর বেশির ভাগ word একই, তবু আমরা প্রতিবার শূন্য থেকে গুনছি। offset-ভিত্তিক sliding window সেই count incremental রাখে — বাঁয়ের word বাদ, ডানের যোগ।

11. Key observation

মূল observation: word সমান-দৈর্ঘ্যের বলে শুরু-position-গুলো মাত্র Lটা phase-এ পড়ে। প্রতিটা phase-এ string-কে word-একক ধাপে হাঁটলে একটা সাধারণ "fixed-window, count মেলাও" sliding window-এ নেমে আসে — যেখানে window slide করলে শুধু এক word বাদ, এক word যোগ।

12. Optimized intuition

need = Counter(words), L = word_len, k = num_words। প্রতিটা offset (0..L-1)-এর জন্য left = offset, খালি window, count = 0। right কে offset থেকে L ধাপে বাড়াও, প্রতিবার word = s[right:right+L]: word need-এ থাকলে window-এ যোগ আর count += 1; যদি কোনো word চাহিদার বেশি হয়, বাঁ দিক থেকে word বাদ দিতে দিতে (left += L) ঠিক করো; count == k হলে left একটা valid শুরু-index। word need-এ না থাকলে window সম্পূর্ণ রিসেট করে left = right + L। মোট O(L · (n/L)) = O(n) word-ছোঁয়া।

13. Thinking tweak

মোচড়: যখন সব টুকরো সমান-দৈর্ঘ্যের, character-একক না ভেবে token-একক ভাবো — string-কে word-এর sequence ধরে fixed-window sliding চালাও, আর Lটা phase আলাদা করে দেখো। এটা Minimum Window Substring-এর tweak-এর উপরে আরেক স্তর: alphabet বদলে গেছে অক্ষর থেকে word-এ, আর window হয়ে গেছে fixed-length।

14. Step-by-step dry run

Input s = "barfoo", words = ["foo","bar"]; L=3, k=2, need = {foo:1, bar:1}, offset 0:

  1. left=0, window={}, count=0।
  2. right=0: word = "bar", need-এ আছে → window={bar:1}, count=1। count != k।
  3. right=3: word = "foo", need-এ আছে → window={bar:1, foo:1}, count=2। count == k → left=0 valid → উত্তরে 0।
  4. offset 1, 2-তে word সারিবদ্ধ হয় না → কিছু যোগ হয় না।
  5. উত্তর: [0]।

15. Python solution

from collections import Counter

def find_substring(s, words):
    if not s or not words:
        return []
    word_len = len(words[0])             # L: প্রতিটা word সমান-দৈর্ঘ্য
    num_words = len(words)               # k
    need = Counter(words)                # word -> কতবার লাগবে
    result = []
    for offset in range(word_len):       # L টা phase / সারিবদ্ধতা
        left = offset
        count = 0
        window = Counter()
        for right in range(offset, len(s) - word_len + 1, word_len):
            word = s[right:right + word_len]
            if word in need:
                window[word] += 1
                count += 1
                while window[word] > need[word]:     # বেশি হয়ে গেছে → বাঁ টানো
                    left_word = s[left:left + word_len]
                    window[left_word] -= 1
                    left += word_len
                    count -= 1
                if count == num_words:               # ঠিক সব word মিলেছে
                    result.append(left)
            else:                                    # অচেনা word → রিসেট
                window.clear()
                count = 0
                left = right + word_len
    return sorted(result)

# ---- tests ----
assert find_substring("barfoothefoobarman", ["foo", "bar"]) == [0, 9]
assert find_substring("wordgoodgoodgoodbestword", ["word", "good", "best", "word"]) == []
assert find_substring("barfoofoobarthefoobarman", ["bar", "foo", "the"]) == [6, 9, 12]
assert find_substring("", ["a"]) == []
print("সব test pass!")

16. Line-by-line code explanation

  • if not s or not words: return [] — খালি input-এ কোনো valid index নেই।
  • word_len, num_words, need — L, k, আর word-চাহিদার count।
  • for offset in range(word_len) — Lটা সারিবদ্ধতা; প্রতিটায় string-কে word-একক ধাপে দেখি।
  • for right in range(offset, len(s) - word_len + 1, word_len) — L ধাপে এগিয়ে প্রতিটা word-এর শুরু।
  • if word in need: window[word]+=1; count+=1 — চেনা word হলে window-এ যোগ।
  • while window[word] > need[word] — এই word চাহিদার বেশি হলে বাঁ দিক থেকে word বাদ দিয়ে ভারসাম্য ফেরাই।
  • if count == num_words: result.append(left) — ঠিক kটা চেনা word ভরে গেলে left একটা valid শুরু।
  • else: window.clear(); count=0; left=right+word_len — অচেনা word পেলে window ভেঙে তার পরের word থেকে নতুন করে শুরু।

17. Output walkthrough

"barfoothefoobarman", ["foo","bar"]-এ offset 0-তে index 0 (bar+foo) ও 9 (foo+bar) মেলে → [0, 9]। দ্বিতীয় case-এ দুটো "word" কখনো এক block-এ good+best-সহ জোগাড় হয় না → []। তৃতীয় case-এ bar+foo+the-এর নানা ক্রমে index 6, 9, 12 মেলে → sort করে [6, 9, 12]। খালি s-এ []। শেষে print: সব test pass!।

18. Time complexity

O(n · L) worst case (n = len(s), L = word_len) — Lটা offset, প্রতিটায় n/L word, আর shrink-এ প্রতিটা word সর্বোচ্চ একবার বাদ; অনেক বিশ্লেষণে এটাকে O(n · L) ধরা হয়। নাইভ O(n · k) থেকে ভালো যখন k বড়।

19. Space complexity

O(k · L) — need ও window-এ সর্বোচ্চ kটা আলাদা word, প্রতিটা দৈর্ঘ্য L।

20. Common mistakes

  • word পুনরাবৃত্তি ভুলে যাওয়া — set দিয়ে করলে ["word","word"]-এর দুটো word ধরা পড়ে না; Counter লাগবে।
  • সব offset না দেখা — শুধু offset 0 থেকে শুরু করলে যেসব valid block অন্য phase-এ শুরু হয় সেগুলো বাদ পড়ে; range(word_len)-এর প্রতিটা offset চাই।
  • অচেনা word-এ window না ভাঙা — চেনা সীমার বাইরের word এলে window/count/left রিসেট না করলে ভুল ম্যাচ হয়।

21. Which basic problem this inherits from

ভিত্তি: Minimum Window Substring (#20)-এর count-মেলানো sliding window — এখানে alphabet হলো word, window fixed-length, আর Lটা phase আলাদা করে দেখা হয়। মূল frequency counting আসে Pattern 1 থেকে (Valid Anagram #3-এর বংশধর)। সম্পূর্ণ আলোচনা ../patterns.md-র Pattern 1-এ।

22. Similar harder problems

23. Pattern learned

Frequency counting + fixed windows: সব টুকরো সমান-দৈর্ঘ্য হলে token-একক (word) ভাবো; need count বানিয়ে Lটা phase ধরে fixed-window sliding চালাও — baঁ word বাদ, ডান word যোগ, count == k হলেই valid index।

24. Final summary

ভবিষ্যতের আমাকে: "সমান-দৈর্ঘ্যের word/টোকেন পরপর সাজানো আছে কোথায়" শুনলেই word-একক fixed-window + Counter মনে পড়বে, আর Lটা phase আলাদা করার কথা। এটা Minimum Window Substring-এরই বড় ভাই — শুধু অক্ষরের জায়গায় word, আর window fixed। মূল tweak সেই একটাই — count incremental রাখো, শূন্য থেকে গুনো না।

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