010 — Longest Substring Without Repeating Characters

Source

• Original source: Classic sliding-window exercise
• Platform: LeetCode — https://leetcode.com/problems/longest-substring-without-repeating-characters/
• Topic: string / sliding window
• Difficulty: Medium
• Pattern: sliding window (variable size, repair করে চলা)
• Basic idea inherited from: two pointers + frequency counting — একই দিকে চলা দুই pointer, আর কোন char কোথায় দেখেছি তা মনে রাখা

1. Problem in simple words

একটা string s দেওয়া। এর মধ্যে এমন সবচেয়ে লম্বা substring (পরপর থাকা অংশ) খুঁজে বের করো যেখানে কোনো character দুবার নেই। তোমাকে সেই সবচেয়ে লম্বা substring-এর দৈর্ঘ্য ফেরত দিতে হবে।

s = "abcabcbb"
repeat ছাড়া সবচেয়ে লম্বা: "abc"  ->  দৈর্ঘ্য 3

2. Which basic idea does this inherit from?

এটা two pointers আর frequency counting দুটোকেই মেলায়: একটা window [start..i] রাখি যেটা সবসময় unique রাখার চেষ্টা করে। i (ডান প্রান্ত) এগোতে থাকে, আর কোন character শেষ কোথায় দেখেছি সেটা মনে রাখি — duplicate এলে বাঁ প্রান্ত start লাফ দিয়ে সরে repair করি। sliding-window-এর math রূপ ../../01-math-based-programming-fundamentals/06-two-pointers-sliding-window-math/-তে।

3. What is the hidden math or logic?

লুকানো logic: একটা window valid (সব unique) হলে, ডান প্রান্ত এক ঘর বাড়ানোর পর যদি duplicate তৈরি হয়, তবে সেই repeated character-এর আগের অবস্থানের ঠিক পরে পর্যন্ত বাঁ প্রান্ত টেনে আনলেই window আবার valid — মাঝের কোনো অংশ scratch থেকে গোনার দরকার নেই। তাই প্রতিটা index একবার ঢোকে, একবার বের হয় → O(n)।

4. Which data structure is needed?

একটা hash map (dict) last, যেখানে key = character, value = সেই character সর্বশেষ যে index-এ দেখা গেছে। সাথে দুটো integer — start (window-এর বাঁ প্রান্ত) আর best (এ যাবৎ সেরা দৈর্ঘ্য)।

5. Why this data structure fits

Dict-এর lookup average O(1), তাই "এই character কি window-এর ভিতরে আগে দেখেছি, আর কোথায়?" — দুটোই সাথে সাথে জানা যায়। character-এর শেষ index জানা থাকলে বাঁ প্রান্তকে এক লাফেই সঠিক জায়গায় নেওয়া যায়, একটা একটা করে সরাতে হয় না।

6. Real-life analogy

ভাবো তুমি রাস্তায় একটানা দোকান গুনছ, শর্ত — একই নামের দোকান window-তে দুবার থাকতে পারবে না। নতুন দোকান valid হলে window বড় করো। যদি এমন নামের দোকান আসে যেটা আগেই window-তে আছে, তখন বাঁ প্রান্তটা সেই পুরনো দোকানের ঠিক পরে এনে ফেলো — তাহলে আবার সব নাম আলাদা।

7. Visual explanation

s = "abcabcbb" দিয়ে window-এর চলাফেরা:

[a]bcabcbb            window "a"     best 1
[ab]cabcbb            window "ab"    best 2
[abc]abcbb            window "abc"   best 3
a[bca]bcbb   'a' আগে index 0-এ -> start = 0+1, window "bca"  best 3
ab[cab]cbb   'b' আগে index 1-এ -> start = 1+1, window "cab"  best 3
...                    best আর বাড়ে না
answer: 3

8. Example input and output

Input : "abcabcbb" -> 3   ("abc")
Input : "bbbbb"    -> 1   ("b")
Input : "pwwkew"   -> 3   ("wke")

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

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা শুরু-index থেকে যত দূর পর্যন্ত সব character unique থাকে দেখো, প্রতিবার একটা set-এ ভরে check করে।

best = 0
for i in range(n):
    seen = set()
    for j in range(i, n):
        if s[j] in seen: break
        seen.add(s[j])
        best = max(best, j - i + 1)

10. Why brute force is slow

প্রতিটা শুরু-point থেকে আবার সামনে স্ক্যান করা মানে O(n^2) (worst case)। বারবার একই অংশ পুনরায় গোনা হচ্ছে — অথচ window valid রাখলে আগের কাজটুকু ফেলে দেওয়ার দরকার নেই, শুধু বাঁ প্রান্ত সরিয়ে repair করলেই হয়।

11. Key observation

মূল observation: window ভাঙলে (duplicate এলে) পুরো window scratch থেকে শুরু করতে হয় না। repeated character-এর আগের অবস্থানের পরপরই বাঁ প্রান্ত নিয়ে গেলে valid window ফিরে আসে, আর তার ভেতরের কাজ এখনো ঠিক আছে।

12. Optimized intuition

ডান প্রান্ত i এক এক করে এগোও। প্রতিটা character ch-এ দেখো সে আগে কোথায় দেখা গেছে (last[ch])। যদি সেই অবস্থান এখনকার window-এর ভিতরে (>= start) হয়, তবে start = last[ch] + 1 করে window-কে repeat-মুক্ত করো। তারপর last[ch] = i update করে best-কে i - start + 1 দিয়ে বড় করার চেষ্টা করো। এক pass, O(n)।

13. Thinking tweak

মোচড়: "প্রতিটা শুরু থেকে কত দূর যেতে পারি" (O(n^2)) ভুলে গিয়ে ভাবো "একটা valid window রাখব, ভাঙলে শুধু বাঁ প্রান্ত সরিয়ে সারিয়ে নেব।" restart নয়, repair — এটাই sliding window-এর প্রাণ।

14. Step-by-step dry run

Input "abcabcbb":

1. start=0, best=0, last={}। i=0 'a': নতুন → last={a:0}, best=1।
2. i=1 'b': নতুন → last={a:0,b:1}, best=2।
3. i=2 'c': নতুন → last={a:0,b:1,c:2}, best=3।
4. i=3 'a': last[a]=0 >= start 0 → start=1; last[a]=3; দৈর্ঘ্য 3-1+1=3, best=3।
5. i=4 'b': last[b]=1 >= start 1 → start=2; last[b]=4; দৈর্ঘ্য 3।
6. বাকিগুলোতেও best 3-ই থাকে। ফল: 3।

15. Python solution

def length_of_longest_substring(s):
    last = {}                       # char -> শেষ যে index-এ দেখা গেছে
    start = 0                       # window-এর বাঁ প্রান্ত
    best = 0
    for i, ch in enumerate(s):
        if ch in last and last[ch] >= start:
            start = last[ch] + 1    # duplicate-এর পরে window টানো
        last[ch] = i                # এই char-এর শেষ index update
        best = max(best, i - start + 1)
    return best

# ---- tests ----
assert length_of_longest_substring("abcabcbb") == 3    # "abc"
assert length_of_longest_substring("bbbbb") == 1       # "b"
assert length_of_longest_substring("pwwkew") == 3      # "wke"
assert length_of_longest_substring("") == 0            # খালি
assert length_of_longest_substring("au") == 2          # "au"
assert length_of_longest_substring("dvdf") == 3        # "vdf"
print("সব test pass!")

16. Line-by-line code explanation

• last = {} — প্রতিটা character শেষ কোথায় দেখেছি তার map।
• start = 0 — বর্তমান unique window-এর বাঁ প্রান্ত।
• for i, ch in enumerate(s) — ডান প্রান্ত i আর তার character একসাথে।
• if ch in last and last[ch] >= start — character আগে দেখেছি এবং সেটা এখনকার window-এর ভিতরে কিনা; এই দুটো শর্তই জরুরি, নয়তো পুরনো (window-এর বাইরের) দেখা ভুল করে start সরাবে।
• start = last[ch] + 1 — duplicate-এর ঠিক পরে বাঁ প্রান্ত নিয়ে গিয়ে repair।
• last[ch] = i — এই character-এর সর্বশেষ অবস্থান update।
• best = max(best, i - start + 1) — বর্তমান window-এর দৈর্ঘ্য দিয়ে সেরা update।

17. Output walkthrough

"abcabcbb" → "abc" পর্যন্ত best 3, পরে duplicate এলে window slide করে, best 3-ই থাকে → 3, assert pass। "bbbbb" → প্রতিবার start লাফায়, window 1 → 1; "pwwkew" → "wke" দেয় 3; "" → loop চলেই না, 0; "au" → 2; "dvdf" → "vdf" দেয় 3। শেষে print: সব test pass!।

18. Time complexity

O(n) — প্রতিটা character একবার করে process হয়; start কখনো পিছায় না, তাই মোট কাজ linear।

19. Space complexity

O(min(n, k)) — dict-এ আলাদা character-এর সংখ্যা, যেখানে k হলো character set-এর আকার (যেমন ASCII হলে 128)।

20. Common mistakes

• শুধু if ch in last দেখা, last[ch] >= start শর্ত বাদ দেওয়া — তখন window-এর বাইরের পুরনো দেখা ভুল করে start-কে পিছনে টেনে আনে।
• best-কে substring (string) হিসেবে ফেরত দেওয়া — problem শুধু দৈর্ঘ্য চায়।
• window-এর দৈর্ঘ্য i - start লেখা (+1 ভুলে যাওয়া) — দুই প্রান্ত inclusive বলে দৈর্ঘ্য i - start + 1।

21. Which basic problem this inherits from

ভিত্তি: same-direction two pointers (#1 ঘরানা) + frequency/last-seen counting (Two Sum #2-এর "আগে দেখেছি কিনা")। chapter-এর ../patterns.md-এর "Pattern 2 — Sliding Window" দেখো; এটাই পরে Minimum Window Substring (#20)-এর ভিত।

22. Similar harder problems

• Minimum Window Substring (shrinkable window) — https://leetcode.com/problems/minimum-window-substring/ (#20)
• Longest Repeating Character Replacement — https://leetcode.com/problems/longest-repeating-character-replacement/
• Longest Substring with At Most K Distinct Characters — https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/

23. Pattern learned

Sliding window (variable size): "longest/shortest substring/subarray" দেখলে valid window রাখো, ভাঙলে বাঁ প্রান্ত sliding করে repair করো — restart নয়। প্রতিটা index একবার ঢোকে-বেরোয়, O(n)।

24. Final summary

ভবিষ্যতের আমাকে: "unique window রাখো; duplicate এলে start = last[ch]+1; দৈর্ঘ্য = i−start+1।" "repeat ছাড়া longest" বা যেকোনো "longest sub*" দেখলেই sliding window মনে করবে — O(n) time।

25. JavaScript solution (with test cases)

Map দিয়ে last-seen index — duplicate এলে বাঁ প্রান্ত repair করে চলা।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// length of longest substring without repeating chars (sliding window)
function lengthOfLongestSubstring(s) {
  const last = new Map();              // char -> শেষ যে index-এ দেখা গেছে
  let start = 0, best = 0;
  for (let i = 0; i < s.length; i++) {
    const ch = s[i];
    if (last.has(ch) && last.get(ch) >= start) {
      start = last.get(ch) + 1;        // duplicate-এর পরে window টানো
    }
    last.set(ch, i);                   // এই char-এর শেষ index update
    best = Math.max(best, i - start + 1);
  }
  return best;
}
// ---- test cases (example + edge) ----
assert(lengthOfLongestSubstring("abcabcbb") === 3, "abc");
assert(lengthOfLongestSubstring("bbbbb") === 1, "single-repeat");
assert(lengthOfLongestSubstring("pwwkew") === 3, "wke");
assert(lengthOfLongestSubstring("") === 0, "empty");             // edge
assert(lengthOfLongestSubstring("au") === 2, "all-unique");
assert(lengthOfLongestSubstring("dvdf") === 3, "vdf");           // edge
console.log("সব JS test pass!");

JS টীকা: last.get(ch) >= start শর্তটা জরুরি — শুধু last.has(ch) দেখলে window-এর বাইরের পুরনো দেখা ভুল করে start পিছিয়ে দেবে। window দৈর্ঘ্য i - start + 1 (দুই প্রান্ত inclusive)।

26. TypeScript solution (with test cases)

function lengthOfLongestSubstring(s: string): number {
  const last = new Map<string, number>();        // char -> last index
  let start = 0, best = 0;
  for (let i = 0; i < s.length; i++) {
    const ch: string = s[i];
    const prev = last.get(ch);
    if (prev !== undefined && prev >= start) start = prev + 1;
    last.set(ch, i);
    best = Math.max(best, i - start + 1);
  }
  return best;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(lengthOfLongestSubstring("abcabcbb"), 3, "abc");
expect(lengthOfLongestSubstring(""), 0, "empty");
expect(lengthOfLongestSubstring("dvdf"), 3, "vdf");
console.log("সব TS test pass!");

TS টীকা: Map<string, number>.get ফেরত দেয় number | undefined, তাই prev !== undefined দিয়ে narrow করে তবেই prev >= start — index 0-কে ভুল করে "না দেখা" ধরার bug টাইপেই আটকায়।

27. কোথায় কাজে লাগে (real-world use)

• Streaming dedup window: স্ট্রিমে এমন দীর্ঘতম টানা অংশ যেখানে কোনো item পুনরাবৃত্ত নয় (unique-run tracking)।
• Rate limiting / sessions: নির্দিষ্ট শর্ত-মেনে-চলা দীর্ঘতম টানা session ধরা।
• DNA/sequence analysis: repeat ছাড়া দীর্ঘতম substring/segment খোঁজা।
• Network packet inspection: পুনরাবৃত্তি-মুক্ত দীর্ঘতম token sequence বের করা।
• Autocomplete/typing: ইউনিক character-এর দীর্ঘতম টানা ইনপুট অংশ।
• Cache-window analytics: distinct-key-only দীর্ঘতম access window।

মূল pattern: valid window রাখো, ভাঙলে বাঁ প্রান্ত sliding করে repair (restart নয়) — "longest sub*" দেখলেই sliding window, O(n)।

---

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