কনটেন্টে যান

015 — Longest Substring Without Repeating Characters

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

উদাহরণ
string : "abcabcbb"
সেরা substring : "abc"  -> length = 3

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এই 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)।

ভেতরের যুক্তি

লুকানো 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, তার সর্বোচ্চটাই উত্তর।

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য 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)

কোথায় বেশি কাজ হচ্ছে

দুটো 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)-এ জানা যেত।

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

বাঁ থেকে ডান 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)।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

"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={a:3,b:6,c:5}          len=2  best=3
right=7 'b': 'b' আগে index 6 (>=left) -> left=7
             window "b"     last={a:3,b:7,c:5}          len=1  best=3

উত্তর: 3

ছোট input-এ ধাপে ধাপে

Input "pwwkew":

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

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

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

Output মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।