Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
0 like 0 dislike
430 views
in Coding Questions by Goeduhub's Expert (2.3k points)

Given a string, find the length of 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.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 

Restrictions-
Solve the question in O(n) time only.

Goeduhub's Top Online Courses @Udemy

For Indian Students- INR 360/- || For International Students- $9.99/-

S.No.

Course Name

 Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence

Apply Coupon

2.

Natural Language Processing-NLP with Deep Learning in Python Apply Coupon

3.

Computer Vision OpenCV Python | YOLO| Deep Learning in Colab Apply Coupon
    More Courses

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
edited by
 
Best answer

We will be using sliding window here such that we will increase the size of sliding window by 1 for every unqiue char we encounter and if we encounter a seen char we shift the left side of window to seen char index + 1 .


eg : a b c a b c b b       
     ^   ^ 
     |   | 
by this point we havent encounterd any repeating char so we are just moving the right part of sliding window . Now as we encounter a repeating variable "a", we will move the left part of window to index of last 'a' + 1. 
  a b c a b c b b  
    ^   ^ 
    |   |
and so on until the right part of array finishes the input string.
class Solution:
    def lengthOfLongestSubstring(self, s):
        encountered = dict()
        anchor = length = 0
        for i, c in enumerate(s):
            if c in encountered and encountered[c] >= anchor:
                anchor = encountered[c] + 1
            else:
                length = max(length, i + 1 - anchor)
            encountered[c] = i
        return length

3.3k questions

7.1k answers

394 comments

4.6k users

Related questions

0 like 0 dislike
1 answer 228 views
asked Sep 4, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 1.8k views
0 like 0 dislike
1 answer 630 views
0 like 0 dislike
1 answer 554 views
0 like 0 dislike
1 answer 173 views

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...