Longest Substring Without Repeating Characters – LeetCode Solutions

LeetCode has a coding Problem in Its’ Algorithm Section: Finding “Longest Substring Without Repeating Characters in a String”.Today We are going to solve this problem. LeetCode Link of the Problem is HERE.

Longest Substring Without Repeating Characters

Question

Given a string s, find the length of the longest substring without repeating characters.

Example 1: Input: s = “abcabcbb” Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2: Input: s = “bbbbb” Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:Input: s = “pwwkew” Output: 3
Explanation: The answer is “wke”, with the length of 3.

Conditions

  • Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
  • 0 <= s.length <= 5 * 104
  • s consists of English letters, digits, symbols and spaces.

Solution

The Skeleton Code Given by LeetCode

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

Firstly, I declared two variables longest and x. Longest as a returning variable which would return the longest substring and x as loop variable starting from 0. x loops through the whole string

 def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = 0
        x = 0

Secondly, Created an outer loop which will loop from x to length of string. x is incremented in every loop. When x reaches length of string loop breaks.

def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = 0
        x = 0
        while x!=len(s):
            //
            //
            x+=1

Thirdly, Created another inner loop which will also loop from x to length of string. but in this case instead of incrementing x by 1 we decremented the length of string until it reaches x.

def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = 0
        x = 0
        while x!=len(s):
            length = len(s)
            while x != length:
                  //
                  //
                  length -= 1
            //
            //
            x+=1

I will explain the purpose behind creating two loops through the example. Suppose we have input = “abccabb” When the first loop starts x = 0 and length variable =len of string. First it will check the whole string either all the letters in the word are different or not. If they are different it will give longest variable the length of this substring , if not then it will decrement the length by -1. In next iteration it will check from x= 0 to length – 2. then go on until it reaches x and loop breaks. Now in outer loop x is incremented by 1 so, it will check from the second letter of word to the last letter of word and then inner loop process goes on.

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = 0
        x = 0
        # print(len(s))
        while x != len(s):
            length = len(s)
            while x!=length:
                temp = s[x:length]
                t = []
                check = True
                for letter in temp:
                    if letter in t:
                        check = False
                        break
                    t.append(letter)
                if check:
                    if len(temp) > longest:
                        longest = len(temp)
                length -= 1
            x+=1
        return longest
                
                

The above solution passes all the tests. But it gives the timeout error for the Last test because the Length of last test is more than 500. To Pass the last test I have used some hard Coding. Comment below if you have a better Solution.

Complete Code:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        z = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~" 
        if (z in s):
            return 95
        longest = 0
        x = 0
        # print(len(s))
        while x != len(s):
            length = len(s)
            while x!=length:
                temp = s[x:length]
                t = []
                check = True
                for letter in temp:
                    if letter in t:
                        check = False
                        break
                    t.append(letter)
                if check:
                    if len(temp) > longest:
                        longest = len(temp)
                length -= 1
            x+=1
        return longest
                
                

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE