015 — Longest Substring Without Repeating Characters¶

Source¶

Original source: Classic cross-topic capstone interview problem (sliding window family)
Platform: LeetCode — https://leetcode.com/problems/longest-substring-without-repeating-characters/
Topic: strings + hashing
Difficulty: Medium
Pattern: Sliding window + hashmap (variable-size window)
Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 02 strings (string-এর উপর একটা চলমান window, character-এর index নিয়ে কাজ) আর 05 hashing (প্রতিটা character শেষ কোথায় দেখেছি তা hashmap-এ রাখা)। দুই tool জোড়া লাগলেই O(n) sliding window।

1. Problem in simple words¶

তোমাকে একটা string দেওয়া আছে। তোমার কাজ: এমন একটা পরপর থাকা (contiguous) substring খুঁজে বের করো, যার ভেতরে কোনো character দু'বার আসেনি — সব আলাদা। আর সেই rule মানা substring-গুলোর মধ্যে সবচেয়ে লম্বাটার দৈর্ঘ্য return করো (substring-টা না, শুধু length)।

string : "abcabcbb"
সেরা substring : "abc"  -> length = 3

2. Which basic idea does this inherit from?¶

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

02 strings থেকে: string-এর উপর বাঁ-থেকে-ডান একটা window (left, right দুটো pointer), আর কোন character কোথায় বসে আছে সেই thinking।
05 hashing থেকে: প্রতিটা character শেষবার কোন index-এ দেখেছি তা একটা hashmap-এ রাখা — যাতে duplicate পেলে O(1)-এ জানা যায় কোথা থেকে window সরাতে হবে।

একা window scan তোমাকে দেয় টুকরো বড়/ছোট করার ক্ষমতা; একা hashmap দেয় "এটা কি আগে দেখেছি, কোথায়" জানার ক্ষমতা। দুটো মিললে O(n)।

3. What is the hidden math or logic?¶

লুকানো logic একটা monotone window invariant: window [left, right]-এর ভেতরে সবসময় সব character আলাদা — এই শর্ত আমরা ভাঙতে দিই না। নতুন character s[right] যোগ করার সময় যদি সে আগে এই window-এর ভেতরেই দেখা থাকে (last[ch] >= left), তাহলে left-কে ঠিক তার পরের ঘরে লাফ দিয়ে নিয়ে যাই: left = last[ch] + 1। এতে duplicate-টা window-র বাইরে পড়ে যায়, invariant আবার ঠিক। প্রতি step-এ window-র দৈর্ঘ্য right - left + 1, তার সর্বোচ্চটাই উত্তর।

4. Which data structure is needed?¶

দুটো জিনিস লাগে — দুটো integer pointer (left, right) window-র সীমানা ধরতে, আর একটা hashmap (last: character → শেষ দেখা index)। pointer দুটো 02 strings-এর window thinking থেকে, hashmap 05 hashing থেকে।

5. Why this data structure fits¶

আমরা প্রতি step-এ জানতে চাই: "এই character কি window-র ভেতরে আগে আছে, আর থাকলে ঠিক কোথায়?" — এটা একটা lookup-by-key প্রশ্ন, hashmap-এর জন্মগত কাজ (05 hashing), O(1)-এ উত্তর। আর window-টা contiguous বলে শুধু দুই প্রান্ত (left, right) মনে রাখলেই চলে, পুরো substring store করতে হয় না (02 strings-এর pointer thinking)। তাই hashmap + দুটো pointer-ই নিখুঁত ফিট।

6. Real-life analogy¶

ভাবো তুমি একটা সরু গলির ভেতর দিয়ে হাঁটছ আর পথে যাকেই দেখছ তার নাম একটা খাতায় লিখছ। নিয়ম: গলিতে একই লোক দু'বার থাকতে পারবে না। নতুন কারো সাথে দেখা হলে, যদি সে আগে থেকেই গলিতে থাকে, তুমি পেছন থেকে ততজন বের করে দাও যতক্ষণ না সেই পুরনো জনটা বাইরে চলে যায়। সারা পথে গলিতে একসাথে সবচেয়ে বেশি যত লোক ছিল — সেটাই উত্তর।

7. Visual explanation¶

"abcabcbb" দিয়ে window-র ([left..right]) নড়াচড়া দেখি:

right=0 'a': window "a"     last={a:0}              len=1  best=1
right=1 'b': window "ab"    last={a:0,b:1}          len=2  best=2
right=2 'c': window "abc"   last={a:0,b:1,c:2}      len=3  best=3
right=3 'a': 'a' আগে index 0 (>=left) -> left=1
             window "bca"   last={a:3,b:1,c:2}      len=3  best=3
right=4 'b': 'b' আগে index 1 (>=left) -> left=2
             window "cab"   last={a:3,b:4,c:2}      len=3  best=3
right=5 'c': 'c' আগে index 2 (>=left) -> left=3
             window "abc"   last={a:3,b:4,c:5}      len=3  best=3
right=6 'b': 'b' আগে index 4 (>=left) -> left=5
             window "cb"    last={...,b:6}          len=2  best=3
right=7 'b': 'b' আগে index 6 (>=left) -> left=7
             window "b"     last={...,b:7}          len=1  best=3

উত্তর: 3

8. Example input and output¶

Input : "abcabcbb"   -> Output: 3    # "abc"
Input : "bbbbb"      -> Output: 1    # "b"
Input : "pwwkew"     -> Output: 3    # "wke" (মনে রেখো "pwke" subsequence, substring না)

Edge case 1 (খালি string): Input: ""   -> Output: 0
Edge case 2 (সব আলাদা):    Input: "au" -> Output: 2

9. Brute force thinking¶

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য substring (i থেকে j) ধরো, চেক করো তার সব character আলাদা কিনা, আলাদা হলে length মনে রাখো।

for i in range(n):
    for j in range(i, n):
        if all chars in s[i..j] are distinct:
            best = max(best, j - i + 1)

10. Why brute force is slow¶

দুটো nested loop (i, j) সব substring ধরে — O(n^2)-টা, আর প্রতিটার "সব আলাদা?" check আবার O(n) (একটা set ভরে দেখা)। মোট O(n^3) (set caching করলে O(n^2))। মূল অপচয়: একটা character window-র ভেতরে আছে কিনা তা বারবার নতুন করে যাচাই করা — অথচ সেটা hashmap (05) মনে রাখলে O(1)-এ জানা যেত।

11. Key observation¶

মূল observation: যখন একটা duplicate character পাও, পুরো window নতুন করে শুরু করার দরকার নেই — শুধু left-কে আগের duplicate-এর ঠিক পরের ঘরে লাফ দেওয়াও যথেষ্ট। মাঝখানের সব character এখনো valid, তাদের ফেলে দিলে কাজ নষ্ট হয়। এই "left কে jump করানো" চিন্তাই O(n^3) থেকে O(n)-এ নামায়।

12. Optimized intuition¶

বাঁ থেকে ডান right একবার হাঁটাও। প্রতিটা নতুন character-এর শেষ-দেখা index last-এ রাখো। s[right] যদি বর্তমান window-র ভেতরেই আগে দেখা থাকে (last[ch] >= left), left-কে last[ch] + 1-এ সরাও — এতে duplicate বাদ। প্রতি step-এ window length right - left + 1 হিসাব করে best-এ সবচেয়ে বড়টা জমাও। right একবারই পুরো string পার করে — তাই O(n)।

13. Thinking tweak¶

মোচড়: "প্রতিটা substring আলাদা করে পরীক্ষা করব" ভাবার বদলে ভাবো "একটাই window রাখব, যার ভেতরে কখনো duplicate ঢুকতে দেব না।" duplicate দেখলেই বাঁ প্রান্তটা ঠিক ততটুকু সরিয়ে দাও যতটুকু লাগে — পুরো O(n^2) search একটা single-pass window-এ গলে যায়।

14. Step-by-step dry run¶

Input "pwwkew":

শুরু: left = 0, best = 0, last = {}
right=0 'p': window "p", last={p:0}, len 1, best=1
right=1 'w': window "pw", last={p:0,w:1}, len 2, best=2
right=2 'w': 'w' আগে index 1 (>= left=0) → left=2; window "w", last={p:0,w:2}, len 1, best=2
right=3 'k': window "wk", last={...,k:3}, len 2, best=2
right=4 'e': window "wke", last={...,e:4}, len 3, best=3
right=5 'w': 'w' আগে index 2 (>= left=2) → left=3; window "kew", len 3, best=3
Loop শেষ → return best = 3

15. Python solution¶

def length_of_longest_substring(s):
    last = {}                       # character -> শেষ দেখা index
    left = 0                        # window-র বাঁ প্রান্ত
    best = 0                        # সবচেয়ে বড় valid window length
    for right, ch in enumerate(s):
        # ch যদি বর্তমান window-র ভেতরেই আগে থাকে, left-কে লাফ দেওয়াও
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right            # ch-এর শেষ দেখা index আপডেট
        best = max(best, right - left + 1)   # পথের সেরা length
    return best

# ---- tests ----
assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("bbbbb") == 1     # সব একই
assert length_of_longest_substring("pwwkew") == 3
assert length_of_longest_substring("") == 0          # খালি string
assert length_of_longest_substring("au") == 2        # সব আলাদা
assert length_of_longest_substring("dvdf") == 3      # left jump test
assert length_of_longest_substring("tmmzuxt") == 5   # "mzuxt"
print("সব test pass!")

16. Line-by-line code explanation¶

last = {} — character → শেষ index রাখার hashmap (05 hashing)।
left = 0 — window-র বাঁ প্রান্ত; এখান থেকে right পর্যন্ত সব আলাদা।
best = 0 — খালি string হলেও সঠিক 0 দেয়।
for right, ch in enumerate(s) — ডান প্রান্ত একবার scan (02 strings-এর single pass)।
if ch in last and last[ch] >= left — duplicate কি বর্তমান window-র ভেতরে? পুরনো (window-র বাইরের) দেখা গোনায় ধরা যাবে না, তাই >= left শর্তটা জরুরি।
left = last[ch] + 1 — বাঁ প্রান্তকে duplicate-এর ঠিক পরে লাফ দাও।
last[ch] = right — এই character-এর শেষ index আপডেট।
best = max(best, right - left + 1) — বর্তমান window length, সেরাটা জমাও।
return best — পুরো string দেখার পর সবচেয়ে লম্বা valid window।

17. Output walkthrough¶

"abcabcbb"-এ প্রথম তিন step-এ window "abc" হয়ে best=3। এরপর প্রতিটা পুনরাবৃত্ত character left-কে সামনে ঠেলে দেয়, কিন্তু window আর 3-র বেশি বড় হতে পারে না, তাই return 3 — assert pass। "bbbbb"-এ প্রতিবার left লাফায়, window সবসময় 1, return 1। খালি string-এ loop চলেই না, return 0। শেষে print: সব test pass!।

18. Time complexity¶

O(n) — right পুরো string-এ ঠিক একবার এগোয়, left-ও কখনো পিছোয় না (মোট মিলে n বার সামনে যায়), প্রতি step-এ hashmap কাজ O(1)।

19. Space complexity¶

O(min(n, k)) — hashmap-এ একসাথে যত আলাদা character থাকতে পারে (k = alphabet size, বা string ছোট হলে n)। শুধু character set-এর সমান, পুরো substring store করতে হয় না (02 strings + 05 hashing-এর মিতব্যয়িতা)।

20. Common mistakes¶

if ch in last লিখে >= left শর্তটা ভুলে যাওয়া — তখন window-র বাইরের পুরনো দেখা-ও left-কে পেছনে টেনে নেয়, window ভুল ছোট হয় (যেমন "abba")।
substring আর subsequence গুলিয়ে ফেলা — এখানে character পরপর থাকতে হবে, এদিক-ওদিক থেকে তুলে নেওয়া যাবে না।
length হিসাবে right - left লেখা — সঠিক right - left + 1 (দুই প্রান্তই inclusive)।

21. Which basic problem this inherits from¶

ভিত্তি: string-এর উপর variable-size window চালানো (02 strings-এর ../../02-arrays-and-strings/, window family) + character → index রাখার hashmap (05 hashing-এর ../../05-hashing/)। এই দুটো cold অবস্থায় জানা থাকলে এই sliding window নিজে থেকেই দাঁড়িয়ে যায়।

22. Similar harder problems¶

Longest Substring with At Most K Distinct Characters (window invariant একটু আলাদা — at most k key) — https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
Minimum Window Substring (একই window + hashmap, কিন্তু "shortest covering") — https://leetcode.com/problems/minimum-window-substring/
Longest Repeating Character Replacement — https://leetcode.com/problems/longest-repeating-character-replacement/

23. Pattern learned¶

Variable-size sliding window + hashmap: ডান প্রান্ত greedily বাড়াও, একটা invariant ("সব আলাদা") ভাঙলেই বাঁ প্রান্ত ঠিক ততটুকু সরাও, hashmap দিয়ে O(1)-এ "এটা কি ভেতরে আছে, কোথায়" জানো। strings + hashing combo-র canonical রূপ।

24. Final summary¶

ভবিষ্যতের আমাকে: "longest/shortest substring with a condition" দেখলেই sliding window + hashmap মনে করবে — দুটো pointer window সামলায় কোথায়, hashmap সামলায় ভেতরে কী আছে। এখানে last[ch] >= left শর্তটাই আসল চাবি, নাহলে window-র বাইরের পুরনো character ভুল করে গোনায় ঢুকে যায়। strings-scan আর hashmap-lookup-এর সবচেয়ে পরিষ্কার মেলবন্ধন।

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