Leetcode problem - Longest Substring Without Repeating Characters

user_5897079 0
Viewed 172

Question: Given a string s, return the longest palindromic substring in s.

Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Example 2: Input: s = "cbbd" Output: "bb"

My solution is

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
    substr = ''
    length = longest_len = 0
    for ch in s:
        if ch in substr:
            print("substr", substr)
            length = len(substr)
            if length > longest_len:
                longest_len = length
            substr = ''
        substr = substr + ch
    print("substr", substr)
    length = len(substr)
    if length > longest_len:
        longest_len = length        
    return longest_len

Can anyone tell me why is it failing the testcase: enter image description here

How can "dvdf" output be 3, shouldn't it be 2?

substr python-3.x string
2 Answers

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar.

https://en.wikipedia.org/wiki/Palindrome

The longest palindrome of dvdf is dvd.
A palindrome can contain repeating characters, which does not match the title of your question.
Your solution does not check whether a substring is a palindrome.

user_8693300

Accepted Python Answer in LeetCode

I've solved this using the power of lists in Python

The code below is well commented, however, I will explain the key point behind it.

By looping and adding unseen chars in the temporary list until the point where we catch an already found char, then update the max length if it is less than the new length of the temporary list.

The logic after this is for sure to clear up the temporary list, but here is the point, we have to do so if and only if the currently found char is the same as the previously added one in our temp list.

And if that is not the case and if the repeating char is found in a different index, we need to remove the elements from the temp list until the index of the found char. So that, we don't remove already added characters that would be possible to form the largest substring of the original string.

class Solution:
            
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        # temprary list to memorize chars
        temp_list = []
        
        # max length to track the length of the unique chars
        max_len = 0
        
        # loop for each char in s
        for c in s:
            
            if c in temp_list:
                
                # if the current length of the list is greater than the previous one, then update
                if len(temp_list) > max_len:
                    max_len = len(temp_list)
                    
                # if current character is the last added one, then reset 
                if c == temp_list[-1]:
                    temp_list = []    
                else: # in case where the current char found in differnet index, then, remove all elements up to it 
                    temp_list = temp_list[temp_list.index(c)+1:]
                    
                # after process, add the new char    
                temp_list.append(c)
                
            else: # it is a new char, then add it to the list
                temp_list.append(c)
        
        # in case we loop but we don't find repeating characters, then max_len would be zero, so that consider returning len(temp_list)
        return max(max_len, len(temp_list))

Now, to address the test case that you experienced and if you try to print out the temp_list after each time we add a new char in the code above, you will get the following:

['d']

['d', 'v']

['v', 'd']

['v', 'd', 'f']

so that, it is clear that the longest substring is "vdf" and its length is 3

Please let me know if you don't understand any point clearly? Thanks!

user_121465810
Related