Interviewer पूछेगा:
String में बिना repeat वाली सबसे लंबी substring कितनी होगी?
Repeat आया? Window छोटी करो. Let’s make it click.
Train की खिड़की imagine करो. Right से नया character दिखता है. Unique है? खिड़की बढ़ाओ. Duplicate आया? Left side से उतना हिस्सा हटाओ कि फिर सब unique हो जाएँ. Longest valid view याद रखो.
‘abcabcbb’ को सच में चलाकर देखो
पहले a, फिर ab, फिर abc: length 3. अगला a आया तो पुराना a हटाओ; नया window bca. फिर b आया तो cab. Best अब भी 3. Last के repeated b पर window और छोटी होगी. Answer ‘abc’ जैसी substring की length 3 है.
Substring contiguous होती है. Subsequence में gaps allowed होते हैं. अगर problem subsequence पूछती है तो sliding-window answer मत चिपका देना.
Last-seen index से left को jump कराओ
हर character का latest index map में रखो. Current character पहले देखा है तो left = max(left, lastSeen[ch] + 1). फिर lastSeen update करो और best = max(best, right-left+1). max जरूरी है, नहीं तो left पीछे जा सकता है.
‘abba’ classic trap है: last a index 0 था, लेकिन left पहले ही 2 हो चुका है. आखिरी a पर left को 1 कर दिया तो duplicate b वापस window में आ जाएगा. इसलिए left कभी पीछे नहीं जाता.
Nested while दिखा, तो O(n²)? नहीं भाई.
Set-based version में right वाला for और left वाला while nested दिखते हैं. पर left और right दोनों सिर्फ आगे चलते हैं. हर character maximum एक बार add, एक बार remove होता है. Total O(n) expected time, O(min(n, alphabet size)) extra space.
Brute force सभी substrings बनाकर uniqueness हर बार scan करे तो O(n³) तक. Incrementally set बनाए तो O(n²). Window repeated work हटाती है.
Minimum Window में validity बदल जाती है
LC 76 में unique characters नहीं, target की required frequencies पूरी करनी हैं. Right expand करो जब तक valid नहीं; फिर valid रहते हुए left shrink करके minimum record करो. Missing-count या formed-requirements का invariant रखो.
Variable sliding window तभी natural है जब expand/shrink से validity predictable हो. Negative numbers वाले arbitrary sum constraints में naive sum-window fail कर सकती है; prefix sums + hashing या दूसरे tools देखो.
“मैं [left, right] window में unique characters का invariant रखूँगा. Duplicate मिलने पर left को पुराने occurrence के आगे बढ़ाऊँगा, कभी पीछे नहीं. हर right position पर valid length का max रखूँगा. Hash lookups expected O(1), इसलिए O(n) expected time और O(min(n, alphabet)) space.”
Read it once. फिर अपने words में बोल के देखो.Pattern पहचानो.
| Problem में ये दिखे | तब ये use करो | यहाँ नहीं |
|---|---|---|
| Longest substring, no repeat | Last-seen map / set + variable window | Subsequence or noncontiguous selection |
| Smallest window covering target | Frequency map + shrink while valid | Only a set when repeated target counts matter |
| Sum constraint, positive numbers | Monotonic variable window | Negative numbers break the sum monotonicity |
अब code लिखते हैं.
Longest Substring Without Repeating Characters · LC 3
max(left, …) prevents the ‘abba’ bug. O(n) expected time.
def length_of_longest_substring(s):
last_seen = {}
left = best = 0
for right, char in enumerate(s):
left = max(left, last_seen.get(char, -1) + 1)
last_seen[char] = right
best = max(best, right - left + 1)
return best
assert length_of_longest_substring("abcabcbb") == 3
assert length_of_longest_substring("abba") == 2Practice करो. Confidence आएगा.
Your progress stays on this device. Solve first, tick later. तू खुद से cheat मत करना.
कल interview है? ये साथ ले जाओ.
Day 4 का full guide — concepts, patterns, code और practice, एक PDF में.
अभी भी doubt है?
Empty string का answer?+
0. Loop नहीं चलेगा और best = 0 return होगा.
Unicode emoji के लिए same code?+
Python code Unicode code points track करता है; Java char UTF-16 units और C++ string bytes track करते हैं. User-visible grapheme clusters चाहिए तो पहले proper Unicode segmentation करो.
Window का invariant बोल सको, तो code खुद निकलता है. Next: fixed-size window में बस subtract और add.