कोडिंग इंटरव्यू: Minimum Window Substring को कैसे हल करें?

समस्या और यह कब लागू होती है

स्ट्रिंग्स s और t दिए जाने पर, s की सबसे छोटी निरंतर सबस्ट्रिंग खोजें जिसमें t का प्रत्येक कैरेक्टर कम से कम उतनी बार शामिल हो जितनी बार वह t में आता है। मिलान केस-संवेदी (case-sensitive) है। उदाहरण के लिए:

s = "ADOBECODEBANC"
t = "ABC"
output = "BANC"

यदि t = "AABC" है, तो एक संभावित विंडो को कम से कम दो A कैरेक्टर, एक B, और एक C की आवश्यकता होती है। सेट-मेंबरशिप जांच इस बहुलता (multiplicity) आवश्यकता को खो देती है, जो इस समस्या में सबसे आम सिमेंटिक गलती है।

प्रतिबंध 1 <= s.length, t.length <= 100000 हैं, और दोनों स्ट्रिंग्स में केवल अपरकेस और लोअरकेस अंग्रेज़ी अक्षर हैं। यदि कोई उत्तर मौजूद है, तो सबसे छोटा उत्तर अद्वितीय होता है। जब कोई विंडो t को कवर नहीं करती है तो एक खाली स्ट्रिंग लौटाएं। नीचे दिया गया कार्यान्वयन खाली t और t से छोटे s को भी रक्षात्मक रूप से संभालता है, यद्यपि वे इनपुट्स मानक प्रतिबंधों से बाहर हैं।

हाल के सार्वजनिक सॉफ़्टवेयर इंजीनियरिंग साक्षात्कार रिकॉर्ड अभी भी Minimum Window Substring दिखाते हैं, जिसमें एक भिन्नता भी शामिल है जहां t में कोई डुप्लिकेट कैरेक्टर नहीं होते हैं। अंग्रेज़ी और चीनी दोनों कोडिंग प्लेटफ़ॉर्म भी इस समस्या को बनाए रखते हैं। इसका मुख्य कौशल एक वैश्विक न्यूनतम-अंतराल खोज को वृद्धिशील रूप से बनाए रखी गई स्थिति (incrementally maintained state) में बदलना है, इसलिए सटीक श्रेणी coding है; उदाहरण की भाषा उस वर्गीकरण को नहीं बदलती है।

इंटरव्यूअर क्या मूल्यांकन कर रहा है

पहला संकेत सटीक मॉडलिंग है। एक मजबूत उत्तर "t शामिल है" को एक फ़्रीक्वेंसी प्रतिबंध के रूप में व्यक्त करता है: प्रत्येक लक्ष्य कैरेक्टर c के लिए, वर्तमान विंडो को window[c] >= need[c] को संतुष्ट करना होगा। केवल यह कहना कि सभी लक्ष्य कैरेक्टर दिखाई दिए हैं, t = "AA" को नहीं संभाल सकता।

दूसरा संकेत द्विघात (quadratic) बेसलाइन के पीछे एकरसता (monotonicity) को पहचानना है। दाएँ किनारे को खिसकाने से केवल कैरेक्टर जुड़ते हैं, इसलिए एक मान्य विंडो विस्तारित होने पर मान्य ही रहती है। एक निश्चित दाएँ किनारे के लिए, बाएँ किनारे को खिसकाने से कैरेक्टर हटते हैं। एक बार जब विंडो मान्य हो जाती है, तो इसे तब तक संकुचित किया जा सकता है जब तक कि यह अभी-अभी अमान्य न हो जाए, रास्ते में छोटे उम्मीदवारों को रिकॉर्ड करते हुए।

तीसरा संकेत वैधता जांच को संपीड़ित करना है। प्रत्येक चाल पर संपूर्ण फ़्रीक्वेंसी तालिका को स्कैन करने से रैखिक (linear) सीमा समाप्त हो जाती है। कार्यान्वयन उन लक्ष्य कैरेक्टर वर्गों की संख्या के लिए formed का उपयोग करता है जिनकी आवश्यक आवृत्ति पूरी हो चुकी है, जिसमें required = need.size है। formed तब बढ़ता है जब कोई आवृत्ति पहली बार अपनी आवश्यकता के बराबर हो जाती है और जब हटाए जाने पर यह उस आवश्यकता से कम हो जाती है तो घट जाती है। अतिरिक्त प्रतियों (surplus copies) को दो बार नहीं गिना जाता है।

अंत में, उम्मीदवार को शुद्धता और सीमाओं को सही ठहराना चाहिए: प्रत्येक दाएँ किनारे के लिए सबसे छोटी मान्य विंडो की जांच क्यों की जाती है, क्यों छोड़े गए बाएँ समापन बिंदु बेहतर भविष्य का उम्मीदवार उत्पन्न नहीं कर सकते हैं, और क्यों प्रत्येक पॉइंटर अधिकतम s.length बार चलता है।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• क्या मिलान केस-संवेदी है? यहाँ यह है। यदि मिलान को केस को नज़रअंदाज़ करना चाहिए, तो पहले सामान्यीकरण (normalization) को परिभाषित करें; सामान्यीकरण मूल स्ट्रिंग में सूचकांकों के मैपिंग को बदल सकता है।
• क्या "शामिल है" t से क्रम को सुरक्षित रखता है? नहीं। इस समस्या को केवल फ़्रीक्वेंसी कवरेज की आवश्यकता है। क्रम की आवश्यकता Minimum Window Subsequence समस्या उत्पन्न करती है, जिसके लिए यह वैधता शर्त काम नहीं करती है।
• क्या डुप्लिकेट लक्ष्य कैरेक्टर अलग से गिने जाते हैं? हाँ। t = "AABC" के लिए दो A कैरेक्टरों की आवश्यकता होती है, जो सीधे एक फ़्रीक्वेंसी मैप को प्रेरित करता है।
• क्या होता है जब कई सबसे छोटी विंडो टाई हो जाती हैं? मानक समस्या विशिष्टता की गारंटी देती है। उस गारंटी के बिना, यह कार्यान्वयन सबसे प्रारंभिक सबसे छोटी विंडो लौटाता है क्योंकि यह केवल सख्ती से छोटी लंबाई पर अपडेट होता है।
• कैरेक्टर सेट क्या है? इनपुट अंग्रेज़ी अक्षर हैं, इसलिए जावास्क्रिप्ट UTF-16 कोड यूनिट्स को इंडेक्स करने से कोई अनुमत कैरेक्टर विभाजित नहीं हो सकता है। मनमाने यूनिकोड के लिए, पहले परिभाषित करें कि मिलान कोड पॉइंट पर संचालित होता है या उपयोगकर्ता द्वारा देखे गए ग्रैफ़ीम क्लस्टर (grapheme clusters) पर।
• क्या कोई भी स्ट्रिंग खाली हो सकती है? मानक प्रतिबंध खाली स्ट्रिंग्स को बाहर रखते हैं। नमूना फ़ंक्शन खाली t, खाली s, या s.length < t.length के लिए एक खाली स्ट्रिंग लौटाता है।
• क्या फ़ंक्शन को टेक्स्ट या इंडेक्स लौटाना चाहिए? मुख्य समस्या टेक्स्ट लौटाती है। इंडेक्स के लिए, कोर स्कैन को बदले बिना [bestStart, bestStart + bestLength) लौटाएं।

ये प्रश्न वैधता विधेय (validity predicate), इंडेक्स प्रतिनिधित्व, या आउटपुट नियम को बदल सकते हैं। भाषा प्राथमिकता, चर नाम, और विशिष्ट हैश-मैप कार्यान्वयन एल्गोरिदम के चयन को नहीं बदलते हैं।

30-सेकंड उत्तर फ़्रेमवर्क

"मैं need में लक्ष्य आवृत्तियों की गणना करूँगा और दो पॉइंटर्स के साथ एक विंडो बनाए रखूँगा। जैसे ही दायाँ पॉइंटर फैलता है, formed केवल तभी बढ़ता है जब एक कैरेक्टर क्लास पहली बार अपनी आवश्यकता तक पहुँचता है। एक बार जब प्रत्येक वर्ग संतुष्ट हो जाता है, तो मैं उत्तर रिकॉर्ड करता हूँ और बाएँ पॉइंटर को तब तक आगे बढ़ाता हूँ जब तक कि विंडो अमान्य न हो जाए। यह प्रत्येक दाएँ समापन बिंदु के लिए सबसे छोटी मान्य विंडो की जांच करता है। दोनों पॉइंटर्स केवल दाईं ओर बढ़ते हैं, इसलिए प्रत्येक स्थिति अधिकतम एक बार प्रवेश करती है और छोड़ती है: O(|s| + |t|) समय और O(u) फ़्रीक्वेंसी-मैप स्थान।"

चरण-दर-चरण गहन विश्लेषण

चरण 1: दोहराए गए कार्य को उजागर करने के लिए बेसलाइन का उपयोग करें।

प्रत्येक बाएँ समापन बिंदु के लिए, आवृत्तियों को बनाए रखते हुए एक दाएँ समापन बिंदु का विस्तार किया जा सकता है और पहली मान्य विंडो पर रुका जा सकता है। यह प्रत्येक सबस्ट्रिंग की पुनर्गणना से बचाता है, लेकिन यह अभी भी प्रत्येक बाएँ समापन बिंदु से s के अधिकांश भाग को फिर से स्कैन कर सकता है, जिसमें O(|s|^2 + |t|) समय लगता है। शुरुआत से प्रत्येक सबस्ट्रिंग की पुनर्गणना क्यूबिक हो सकती है।

यहाँ, u, t में अलग-अलग कैरेक्टरों की संख्या है, जो अंग्रेज़ी-अक्षर प्रतिबंध के तहत अधिकतम 52 है। स्टेट डिज़ाइन लीनियर समाधान का महत्वपूर्ण हिस्सा बना हुआ है; एक छोटा वर्णमाला (alphabet) किसी गलत वैधता जांच को छिपाना नहीं चाहिए।

चरण 2: निरंतर-समय (constant-time) वैधता जांच के लिए पर्याप्त स्थिति परिभाषित करें।

need लक्ष्य आवृत्तियों को संग्रहीत करता है। window वर्तमान विंडो में लक्ष्य कैरेक्टरों की आवृत्तियों को संग्रहीत करता है। required = need.size संतुष्ट करने के लिए कैरेक्टर वर्गों की संख्या है, और formed वह संख्या है जो अपनी आवश्यक आवृत्ति तक पहुँच चुकी है। विंडो ठीक तब मान्य होती है जब formed === required हो।

अपडेट्स को एक आवश्यकता थ्रेशोल्ड को पार करने से जोड़ा जाना चाहिए:

after adding c: window[c] changes from need[c]-1 to need[c], so formed += 1
after adding c: window[c] changes from need[c] to need[c]+1, so formed is unchanged
before removing c: window[c] equals need[c], so removal causes formed -= 1
before removing c: window[c] exceeds need[c], so removal leaves formed unchanged

formed को लक्ष्य कैरेक्टरों की कच्ची गणना के रूप में मानने से अतिरिक्त प्रतियों की अधिक गणना (overcount) होना आसान हो जाता है। योगदान को सीमित किए बिना प्रत्येक लक्ष्य कैरेक्टर पर वृद्धि करने से t = "AABC" को बहुत जल्दी कवर के रूप में गलत तरीके से चिह्नित किया जाएगा।

चरण 3: विस्तार, रिकॉर्डिंग और संकुचन के क्रम को ठीक करें।

दायाँ पॉइंटर s[right] को शामिल करता है और स्थिति को अपडेट करता है। जब विंडो मान्य हो जाती है, तो आंतरिक लूप पहले उत्तर के लिए [left, right] पर विचार करता है और फिर s[left] को हटाने की तैयारी करता है। यदि हटाने से एक कैरेक्टर क्लास में कमी आती है, तो formed को घटाएं, आवृत्ति कम करें, और left को आगे बढ़ाएं।

हटाने से पहले रिकॉर्डिंग किसी मान्य उम्मीदवार को छूटने से रोकती है। आवृत्ति घटाने से पहले समानता का परीक्षण थ्रेशोल्ड संक्रमण को स्पष्ट बनाता है। एक सही कार्यान्वयन पहले घटा सकता है और आवश्यकता से नीचे के मान के लिए परीक्षण कर सकता है, लेकिन स्पष्टीकरण और स्थिति को समान क्रम का उपयोग करना चाहिए।

चरण 4: रैखिक स्कैन लागू करें।

export function minWindow(s: string, t: string): string {
  if (t.length === 0 || s.length < t.length) return "";

  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) ?? 0) + 1);
  }

  const window = new Map<string, number>();
  const required = need.size;
  let formed = 0;
  let left = 0;
  let bestStart = 0;
  let bestLength = Number.POSITIVE_INFINITY;

  for (let right = 0; right < s.length; right += 1) {
    const char = s[right];
    const target = need.get(char);

    if (target !== undefined) {
      const nextCount = (window.get(char) ?? 0) + 1;
      window.set(char, nextCount);
      if (nextCount === target) formed += 1;
    }

    while (formed === required) {
      const length = right - left + 1;
      if (length < bestLength) {
        bestStart = left;
        bestLength = length;
      }

      const leftChar = s[left];
      const leftTarget = need.get(leftChar);
      if (leftTarget !== undefined) {
        const currentCount = window.get(leftChar) ?? 0;
        if (currentCount === leftTarget) formed -= 1;
        window.set(leftChar, currentCount - 1);
      }
      left += 1;
    }
  }

  return Number.isFinite(bestLength)
    ? s.slice(bestStart, bestStart + bestLength)
    : "";
}

कार्यान्वयन केवल लक्ष्य कैरेक्टरों के लिए गणना संग्रहीत करता है। गैर-लक्ष्य कैरेक्टर अभी भी विंडो की लंबाई और उसकी बाईं सीमा को प्रभावित करते हैं, इसलिए उन्हें पहले से s से नहीं हटाया जा सकता है; उन्हें केवल फ़्रीक्वेंसी मैप में प्रविष्टियों की आवश्यकता नहीं होती है।

चरण 5: इनवेरिएंट्स बताएं और शुद्धता सिद्ध करें।

प्रत्येक बाहरी-लूप पुनरावृत्ति के अंत में, निम्नलिखित तथ्य सही होते हैं:

1. window[c] वर्तमान अंतराल [left, right] में लक्ष्य कैरेक्टर c की वास्तविक गणना के बराबर है।
2. formed ठीक उन लक्ष्य वर्गों की संख्या के बराबर है जो window[c] >= need[c] को संतुष्ट करते हैं।
3. आंतरिक लूप समाप्त होने के बाद, वर्तमान विंडो अमान्य है। अभी जांची गई अंतिम मान्य विंडो उस right समापन बिंदु के लिए सबसे छोटी मान्य विंडो थी।
4. left केवल दाईं ओर बढ़ता है। पहले से पार किया गया कोई भी पिछला बायाँ समापन बिंदु उसी दाएँ समापन बिंदु के लिए एक लंबी विंडो बनाएगा, और बाद में दाएँ समापन बिंदु का विस्तार करने से यह उस पिछले समापन बिंदु पर पहले से विचार किए गए उम्मीदवार से बेहतर नहीं हो सकता है।

खाली प्रारंभिक विंडो पहले दो इनवेरिएंट्स को संतुष्ट करती है। सही कैरेक्टर जोड़ने से इसकी वास्तविक गणना अपडेट हो जाती है, और थ्रेशोल्ड नियम दूसरे इनवेरिएंट को सुरक्षित रखता है। जब तक विंडो मान्य होती है, एल्गोरिदम प्रत्येक निष्कासन से पहले उम्मीदवार को रिकॉर्ड करता है, इसलिए यह वर्तमान right पर समाप्त होने वाली सभी मान्य बायीं सीमाओं की जांच करता है जब तक कि पहले दो इनवेरिएंट यह न कहें कि विंडो अमान्य है। दाएँ समापन बिंदुओं पर आगमन (induction) द्वारा, एल्गोरिदम प्रत्येक के लिए सबसे छोटी मान्य विंडो की जांच करता है। वैश्विक इष्टतम (global optimum) उन उम्मीदवारों के बीच होना चाहिए, इसलिए रिकॉर्ड किया गया उत्तर सही है।

चरण 6: डुप्लिकेट कैरेक्टरों वाले लक्ष्य का पता लगाएं।

मान लें कि s = "AAABBC" और t = "AABC":

need = {A:2, B:1, C:1}, required = 3
right=0, A:1  formed=0
right=1, A:2  formed=1
right=2, A:3  formed=1    surplus A does not count twice
right=3, B:1  formed=2
right=4, B:2  formed=2    surplus B does not count twice
right=5, C:1  formed=3    [0,5] is valid
remove A at index 0: A:2, still valid; record [1,5] = "AABBC"
remove another A: A:1, formed falls to 2, so contraction stops

यह ट्रेस तीन स्वतंत्र विवरणों की जांच करता है: एक से अधिक की आवश्यक आवृत्ति, आवश्यकता से अधिक कोई दोहराव नहीं गिनना, और एक अतिरिक्त प्रतिलिपि को हटाने के बाद निरंतर संकुचन।

चरण 7: जटिलता का सटीक विश्लेषण करें।

need का निर्माण t को एक बार स्कैन करता है। दायाँ पॉइंटर s को एक बार स्कैन करता है, और बायाँ पॉइंटर पूरे निष्पादन के दौरान 0 से s.length तक केवल एक बार जा सकता है। इसलिए आंतरिक while लूप का संचयी कार्य O(|s|) है। औसत O(1) मैप संचालन के साथ, कुल समय O(|s| + |t|) है। दो फ़्रीक्वेंसी मैप अधिकतम u लक्ष्य कैरेक्टर संग्रहीत करते हैं, इसलिए अतिरिक्त स्थान O(u) है; अंग्रेज़ी-अक्षर प्रतिबंध के तहत, u <= 52।

चरण 8: एक ऑरेकल और गुणों के साथ सत्यापित करें।

कम से कम, निश्चित परीक्षणों में शामिल होना चाहिए:

("ADOBECODEBANC", "ABC") -> "BANC"   standard mixed input
("AAABBC", "AABC")       -> "AABBC"  duplicate requirement
("a", "a")               -> "a"      minimum size
("a", "A")               -> ""       case-sensitive and impossible
("abc", "abcd")          -> ""       s is shorter than t
("abc", "")              -> ""       defensive empty target

लघु यादृच्छिक स्ट्रिंग्स के लिए, प्रत्येक अंतराल की गणना करने वाले द्विघात ऑरेकल के विरुद्ध तुलना करें। अनुकूलित परिणाम के तीन गुणों की जांच करें: यह s का एक सन्निहित सबस्ट्रिंग है, इसकी आवृत्तियाँ t को कवर करती हैं, और कोई भी छोटा अंतराल t को कवर नहीं करता है। विभेदक परीक्षण (differential testing) विशेष रूप से अधिक गिने गए formed, ऑफ़-बाय-वन उत्तर लंबाई और गलत निष्कासन क्रम को उजागर करने में प्रभावी है।

जब s बहुत छोटा होता है, ऑपरेशन एक बार का होता है, और प्रदर्शन अप्रतिबंधित होता है, तो द्विघात संस्करण छोटा होता है और साक्षात्कार के दबाव में लिखना अधिक सुरक्षित हो सकता है। 100000 की लंबाई सीमा और एक स्पष्ट रैखिक-समय लक्ष्य के साथ, स्लाइडिंग विंडो उपयुक्त अंतिम समाधान है।

उच्च-गुणवत्ता वाला नमूना उत्तर

"मैं पहले पुष्टि करूँगा कि समावेशन कैरेक्टर आवृत्तियों पर आधारित है, क्रम कोई मायने नहीं रखता, और मिलान केस-संवेदी है। एक बेसलाइन प्रत्येक बाएँ समापन बिंदु को ठीक करता है और दाईं ओर फैलता है, जो सबसे खराब स्थिति में द्विघात होता है। इस समस्या में उपयोगी एकरसता है: एक दायाँ कैरेक्टर जोड़ने से एक मान्य विंडो अमान्य नहीं हो सकती है, और एक बार विंडो मान्य होने के बाद, बाएँ समापन बिंदु को आगे बढ़ाने से उस दाएँ समापन बिंदु पर समाप्त होने वाली सबसे छोटी मान्य विंडो मिल सकती है।

मैं need में t आवृत्तियों को और window में वर्तमान लक्ष्य आवृत्तियों को संग्रहीत करूँगा। मैं formed को भी बनाए रखूँगा, जो उन कैरेक्टर वर्गों की संख्या है जो अपनी आवश्यकता तक पहुँच चुके हैं। एक कैरेक्टर जोड़ने पर formed केवल तभी बढ़ता है जब उसकी गणना बिल्कुल आवश्यक गणना बन जाती है। जब तक विंडो मान्य होती है, मैं बाएँ कैरेक्टर को हटाने से पहले इसे रिकॉर्ड करता हूँ। यदि वह कैरेक्टर हटाने से पहले अपनी आवश्यक गणना पर है, तो हटाने से वर्ग में कमी आ जाती है, इसलिए मैं formed को घटाता हूँ।

प्रमुख इनवेरिएंट यह हैं कि window, [left, right] में सही गणनाओं से मेल खाता है और formed संतुष्ट लक्ष्य वर्गों की संख्या से मेल खाता है। आंतरिक लूप प्रत्येक दाएँ समापन बिंदु के लिए प्रत्येक मान्य बायीं सीमा की जांच करता है और सबसे छोटे मान्य को पार करने के ठीक बाद रुक जाता है। वैश्विक इष्टतम उन उम्मीदवारों के बीच है। दोनों पॉइंटर्स केवल दाईं ओर बढ़ते हैं, इसलिए प्रत्येक स्थिति अधिकतम एक बार प्रवेश करती है और छोड़ती है। समय O(|s| + |t|) है और स्थान O(u) है। मैं ब्रूट-फ़ोर्स ऑरेकल के विरुद्ध डुप्लिकेट लक्ष्य, कोई समाधान नहीं, एक-कैरेक्टर इनपुट, केस अंतर और यादृच्छिक छोटी स्ट्रिंग्स का परीक्षण करूँगा।"

सामान्य गलतियाँ

• केवल लक्ष्य कैरेक्टरों का एक सेट संग्रहीत करना → डुप्लिकेट आवश्यकताएं गायब हो जाती हैं → आवश्यक आवृत्तियों को संग्रहीत करें।
• जोड़े गए प्रत्येक लक्ष्य कैरेक्टर के लिए मिलान गणना बढ़ाना → अतिरिक्त प्रतियां गलत वैधता बनाती हैं → केवल आवश्यक गणना में पहले संक्रमण पर formed बढ़ाएं।
• लक्ष्य कैरेक्टर को हटाते समय हमेशा formed घटाना → अतिरिक्त प्रतिलिपि को हटाने से विंडो मान्य रहती है → केवल तभी घटाएं जब पूर्व-निष्कासन गणना आवश्यकता के बराबर हो।
• मान्य होने के बाद केवल एक बार संकुचित करना → समान दाएँ किनारे पर समाप्त होने वाली छोटी विंडो छूट जाती हैं → जब तक विंडो पहली बार अमान्य न हो जाए तब तक while लूप का उपयोग करें।
• उत्तर रिकॉर्ड करने से पहले left को ले जाना → एक मान्य न्यूनतम छूट सकता है या ऑफ़-बाय-वन मापा जा सकता है → पहले [left, right] को मापें।
• प्रत्येक पॉइंटर चाल के बाद सभी need को स्कैन करना → वैधता जांच में u का एक कारक जुड़ जाता है → संतुष्ट-वर्ग गणना को वृद्धिशील रूप से बनाए रखें।
• एक सबसीक्वेंस समस्या को हल करना → परिणाम के अंदर के स्थानों को छोड़ा जा सकता है, इसलिए उत्तर अब निरंतर नहीं रहता है → प्रत्येक विंडो को एक निरंतर इंडेक्स अंतराल के रूप में दर्शाएं।
• गैर-लक्ष्य कैरेक्टरों को फ़िल्टर करना और फिर फ़िल्टर किए गए इंडेक्स के साथ मूल स्ट्रिंग को स्लाइस करना → फ़िल्टर की गई स्थितियां सीधे स्रोत पर वापस मैप नहीं होती हैं → मूल स्ट्रिंग पर पॉइंटर्स रखें और केवल मैप में गैर-लक्ष्यों को अनदेखा करें।
• आंतरिक लूप को द्विघात कहना → यह विश्व स्तर पर एकरस बाएँ पॉइंटर की उपेक्षा करता है → प्रत्येक स्थिति के अधिकतम एक बार छोड़ने पर परिशोधित (amortize) करें।
• केवल मानक उदाहरण का परीक्षण करना → डुप्लिकेट, असंभव मामले और केस संवेदनशीलता अप्रयुक्त रहते हैं → निश्चित प्रतिकूल मामले और एक यादृच्छिक ऑरेकल जोड़ें।

अनुवर्ती प्रश्न और उत्तर

अनुवर्ती 1: कुल मिलान किए गए कैरेक्टरों के बजाय संतुष्ट कैरेक्टर वर्गों की गणना क्यों करें?

कोई भी स्थिति एक सही एल्गोरिदम का समर्थन कर सकती है, लेकिन वर्ग गणना थ्रेशोल्ड संक्रमण को स्पष्ट बनाती है। need[A] = 2 के लिए, वर्ग केवल तब संतुष्ट होता है जब window[A] 1 से 2 में बदल जाता है; तीसरा A उस स्थिति को नहीं बदलता है। निष्कासन स्थिति को केवल तभी रद्द करता है जब गणना 2 से 1 हो जाती है। कुल-कैरेक्टर काउंटर को केवल तब बढ़ना चाहिए जब window[c] <= need[c] हो और एक सममित निष्कासन नियम का उपयोग करना चाहिए, जिसे गलत बताना आसान है।

अनुवर्ती 2: यदि t में कोई डुप्लिकेट कैरेक्टर नहीं है तो क्या सरल किया जा सकता है?

need में प्रत्येक मान 1 है, इसलिए window को लक्ष्य-कैरेक्टर गणनाओं द्वारा या घटना गणनाओं के साथ जोड़े गए सेट द्वारा दर्शाया जा सकता है। एक ही लक्ष्य की दोहराई गई प्रतियां अभी भी विंडो में दिखाई दे सकती हैं, और एक प्रतिलिपि को हटाने से वर्ग संतुष्ट रह सकता है। सामान्य आवृत्ति कार्यान्वयन को बनाए रखने से बहुत कम निरंतर ओवरहेड जुड़ता है और मूल समस्या को सीधे संभाला जाता है।

अनुवर्ती 3: क्या होगा यदि कैरेक्टर t द्वारा निर्दिष्ट क्रम में दिखाई देने चाहिए?

वह Minimum Window Subsequence है। फ़्रीक्वेंसी कवरेज अब वैधता साबित नहीं करता है: s = "cba", t = "abc" की आवृत्तियों को कवर करता है लेकिन इसका क्रम गलत है। एक समाधान प्रत्येक मिलान उपसर्ग के लिए प्रारंभिक स्थिति को बनाए रखने के लिए डायनामिक प्रोग्रामिंग का उपयोग कर सकता है, या उम्मीदवार समापन बिंदुओं के आसपास आगे और पीछे स्कैन कर सकता है। इसकी जटिलता को एक नए विश्लेषण की आवश्यकता है, और formed === required को वैधता शर्त के रूप में पुन: उपयोग नहीं किया जा सकता है।

अनुवर्ती 4: आप प्रत्येक टाई हुई सबसे छोटी विंडो को कैसे लौटाएंगे?

विशिष्टता की गारंटी के बिना, पहले की तरह bestLength बनाए रखें। जब कोई छोटी विंडो दिखाई देती है, तो परिणाम सूची को साफ़ करें और उस अंतराल को जोड़ें। जब समान लंबाई की विंडो दिखाई देती है, तो उसे जोड़ें (append)। यदि अलग-अलग खोज पथ एक ही टेक्स्ट अंतराल को फिर से खोज सकते हैं, तो [left, right] द्वारा डिडुप करें; यह दो-पॉइंटर ट्रैवर्सल प्रत्येक अंतराल पर अधिकतम एक बार जाता है, इसलिए यहाँ किसी अतिरिक्त सेट की आवश्यकता नहीं है।

अनुवर्ती 5: क्या होगा यदि s एक कैरेक्टर स्ट्रीम है जो मेमोरी में फिट नहीं हो सकती है?

आवश्यक आवृत्तियों और पॉइंटर स्थिति को अभी भी ऑनलाइन अपडेट किया जा सकता है, लेकिन मूल टेक्स्ट को वापस करने के लिए वर्तमान उम्मीदवार अंतराल को बनाए रखने की आवश्यकता होती है। एक कतार वैश्विक ऑफ़सेट के साथ नवीनतम स्थिति के माध्यम से left से कैरेक्टरों को संग्रहीत कर सकती है। यदि लंबे समय तक कोई मान्य विंडो दिखाई नहीं देती है, तो वह बफ़र अब तक पढ़ी गई पूरी स्ट्रीम तक पहुँच सकता है। केवल लंबाई और ऑफ़सेट लौटाने से लक्ष्य-कैरेक्टर स्थितियों के आसपास अधिक संपीड़न की अनुमति मिलती है; टेक्स्ट लौटाने के लिए एक स्पष्ट अधिकतम-विंडो या बाहरी-स्टोरेज नीति की आवश्यकता होती है।

अनुवर्ती 6: आप मनमाने यूनिकोड टेक्स्ट का समर्थन कैसे करेंगे?

पहले मिलान की इकाई को परिभाषित करें। यूनिकोड कोड पॉइंट के लिए, कोड पॉइंट द्वारा पुनरावृति करें और मूल जावास्क्रिप्ट स्ट्रिंग को स्लाइस करने के लिए संबंधित UTF-16 कोड-यूनिट ऑफ़सेट बनाए रखें। उपयोगकर्ता द्वारा देखे गए कैरेक्टर में कई कोड पॉइंट हो सकते हैं; ग्रैफ़ीम क्लस्टर्स के मिलान के लिए एक विश्वसनीय सेगमेंटर की आवश्यकता होती है। सामान्यीकरण कैरेक्टर समानता की परिभाषा को भी बदलता है, इसलिए स्रोत टेक्स्ट में मैपिंग को संरक्षित करते हुए गणना करने से पहले इसे लगातार लागू किया जाना चाहिए।

अनुवर्ती 7: आप यादृच्छिक परीक्षण ऑरेकल पर कैसे भरोसा कर सकते हैं?

ऑरेकल केवल छोटी स्ट्रिंग्स पर चलता है, इसलिए यह प्रत्येक [left, right] की गणना कर सकता है, प्रत्येक अंतराल को सीधे पुनर्गणना कर सकता है, और लंबाई और प्रारंभिक स्थिति के आधार पर चयन कर सकता है। इसका नियंत्रण प्रवाह जानबूझकर अनुकूलित एल्गोरिदम से अलग है, जिससे यह धीमा लेकिन ऑडिट करने में आसान हो जाता है। ऑरेकल को पहले निश्चित उदाहरणों पर मान्य करें, फिर साझा बग की संभावना को कम करने के लिए यादृच्छिक विभेदक परीक्षणों के दौरान परिणाम की लंबाई, निरंतरता और फ़्रीक्वेंसी कवरेज की तुलना करें।