To find the longest substring without repeating characters : एक स्ट्रिंग को देखते हुए, वर्णों को दोहराए बिना सबसे लंबे सबस्ट्रिंग की लंबाई ज्ञात करें
Example 1
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Check All Leetcode Soulution Explanations
Example 3
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
ध्यान दें कि उत्तर एक सबस्ट्रिंग होना चाहिए, “pwke” एक अनुवर्ती ( subsequence ) है और एक सबस्ट्रिंग नहीं है।
Longest Substring Without Repeating Characters Explanation ( स्पष्टीकरण )
समस्या को हल करने के लिए हम Two Pointers तकनीक का उपयोग करते हैं। एक स्लो पॉइंटर i, एक फास्ट पॉइंटर j .
दोहराए जाने वाले वर्णों का पता लगाने में सहायता के लिए जे पॉइंटर द्वारा देखे गए वर्णों को संग्रहीत करने के लिए हम HashSet भी जोड़ते हैं।
हम जे पॉइंटर को आगे बढ़ाते रहते हैं।
- यदि वर्तमान s.charAt(j) वर्ण हैशसेट में नहीं है, तो हम वर्ण को हैशसेट में जोड़ते हैं और j को आगे बढ़ाते रहते हैं।
- यदि वर्तमान s.charAt(j) वर्ण हैशसेट में है, तो हम उस वर्ण को हटा देते हैं जिस पर मैं जा रहा हूं और i को आगे बढ़ाता हूं। इस बिंदु पर, हमने इंडेक्स i के साथ डुप्लिकेट वर्णों के बिना सबस्ट्रिंग्स का अधिकतम आकार पाया। हम i सूचक को एक कदम आगे ले जाते हैं।
जब j पॉइंटर स्ट्रिंग के सभी वर्णों को पुनरावृत्त करता है, तो हमें वर्णों को दोहराए बिना सबसे लंबे सबस्ट्रिंग की अधिकतम लंबाई मिलती है।
Longest Substring Without Repeating Characters Java Solution
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
HashSet<Character> set = new HashSet<>();
int i = 0;
int j = 0;
while (j < s.length()) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j));
j++;
maxLength = Math.max(maxLength, j - i);
} else {
set.remove(s.charAt(i));
i++;
}
}
return maxLength;
}
}Longest Substring Without Repeating Characters Python Solution
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
counter = {}
j = 0
longest = 0
for i in range(len(s)):
while j < len(s) and s[j] not in counter:
longest = max(longest, j - i + 1)
counter[s[j]] = counter.get(s[j], 0) + 1
j += 1
counter[s[i]] -= 1
if counter[s[i]] == 0:
del counter[s[i]]
return longest- Time complexity: O(n).
- Space complexity: O(m). m is the size of the charset.
Welcome to HindiTutorials, your go-to platform for learning and mastering concepts in Hindi! Our mission is to make education accessible and simple for everyone by providing high-quality tutorials on programming, technology, and various other topics.