CODEWITHSUNDEEP
pythonalgorithm
Melissa Stewart
Melissa Stewart

Reputation: 3605

Longest substring without repeating characters in python

This is a pretty standard interview question. Find the longest substring without repeating characters. Here are the test cases,

abcabcbb -> 3
bbbbb -> 1
pwwkew -> 3
bpfbhmipx -> 7
tmmzuxt -> 5

Here's my code which uses a pretty simple approach with 2 pointers.

def lengthOfLongestSubstring(s):
    checklist = {}
    starting_index_of_current_substring = 0
    length_of_longest_substring = 0
    for i, v in enumerate(s):
        if v in checklist:
            starting_index_of_current_substring = checklist[v] + 1
        else:
            length_of_current_substring = i - starting_index_of_current_substring + 1
            length_of_longest_substring = max(length_of_current_substring, length_of_longest_substring)

        checklist[v] = i
    return length_of_longest_substring

My code passes all the test cases except the last one (actual 4, expected 5). Can someone help me modify the code to take care of the last test case. I don't wish to reinvent the algorithm.

Upvotes: 3

Views: 4708

Answers (7)

Paige Thompson
Paige Thompson

Reputation: 29

I came up with an idiomatic way to do this with sets in Python:

        (lambda whole_str: [                                                                                                                                               
        "".join(whole_str[0:index])                                                                                                                                    
            for index in range(len(whole_str)) if sorted(set(sorted(                                                                                                       
                "".join(whole_str[:index]).replace(" ", "")))) == sorted(                                                                                              
                    "".join(whole_str[:index]).replace(" ", ""))])(                                                                                                    
                        "the quick brown fox jumped over the lazy dog").pop()

This will give you:

Out[1]: 'the quick brown f'

If you don't want to use the lambda closure this will accomplish the same thing:

        ["".join("the quick brown fox jumped over the lazy dog"[0:index])                                                                                                  
           for index in range(len("the quick brown fox jumped over the lazy dog")) if sorted(set(sorted(                                                                     
             "".join("the quick brown fox jumped over the lazy dog"[:index]).replace(" ", "")))) == sorted(                                                            
                 "".join("the quick brown fox jumped over the lazy dog"[:index]).replace(" ", ""))].pop()

Upvotes: -1

Pardeep Beniwal
Pardeep Beniwal

Reputation: 63

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    x = []
    k = 0
    for i, c in enumerate(s):
        if c not in x:
            x.append(c)
        else:            
            x=[c]
        l = len(x)
        k = k if k > l else l 
    return k

o=Solution()
print(o.lengthOfLongestSubstring('abcabcdf'))

Upvotes: 0

sagarjain1991
sagarjain1991

Reputation: 9

Time and Space Management Optimised:

def lengthOfLongestSubstring(self, s: str) -> int:
    curlen = maxlen = 0 # curlen saves the max len of substrings ending with current num
    for i, num in enumerate(s):
        curlen -= s[i-curlen:i].find(num)
        maxlen = max(maxlen, curlen)
    return maxlen

Upvotes: 0

amardip kumar
amardip kumar

Reputation: 27

Find Longest Substring in the string without repeating characters.


def find_non_repeating_substring(input_str):
    output_length = 0
    longest_sub_str = ''
    len_str = len(input_str)
    index = 0
    while len_str != 1:
        l_str = ''
        for i in range(index, len(input_str)):
            if input_str[i] not in l_str:
                l_str = l_str + input_str[i]
            else:
                break
        
        sub_str_length = len(l_str)
        if sub_str_length >  output_length:
            output_length = sub_str_length
            longest_sub_str = l_str
        len_str = len_str -1
        index = index + 1
    return output_length,longest_sub_str
if __name__ == '__main__':
    input_str = raw_input("Please enter the string: ")
    sub_str_length, sub_str = find_non_repeating_substring(input_str)
    print ('Longest Substing lenght is "{0}" and the sub string is "{1}"'.format(sub_str_length, sub_str))```

Upvotes: 0

user11751463
user11751463

Reputation:

This post is pretty old, but I think my solution fixes the bug in the original code.

def lengthOfLongestSubstring(s):
    checklist = {}
    starting_index_of_current_substring = 0
    length_of_longest_substring = 0
    for i, v in enumerate(s):
        if v in checklist:
          if checklist[v] >= starting_index_of_current_substring:
                        starting_index_of_current_substring = checklist[v] + 1

        length_of_current_substring = i - starting_index_of_current_substring + 1
        length_of_longest_substring = max(length_of_current_substring, length_of_longest_substring)
                checklist[v] = i
     return length_of_longest_substring

Upvotes: 2

yedpodtrzitko
yedpodtrzitko

Reputation: 9359

This doesnt really iterate upon your solution, but it's a bit simpler approach, just to give you an idea how it could be also solved.

def longest_substr(s):
    longest = 0
    for start_index in range(len(s)):
        contains = set()
        for letter in s[start_index:]:
            if letter in contains:
                break
            contains.add(letter)
        longest = max(longest, len(contains))
    return longest

Upvotes: 1

JRG
JRG

Reputation: 4177

Here is a simple tweak in your code with 2 pointers to find the longest sub-string without repeating characters.

Change in your code is instead of calculating the length of longest substring when v is not present in checklist, I am calculating length of longest substring for all cases.

def lengthOfLongestSubstring(s):
    checklist = {}
    starting_index_of_current_substring = 0
    length_of_longest_substring = 0
    for i, v in enumerate(s):
        if v in checklist:
            starting_index_of_current_substring = max(starting_index_of_current_substring, checklist[v] + 1)
        checklist[v] = i
        length_of_longest_substring = max(length_of_longest_substring, i - starting_index_of_current_substring + 1)
    return length_of_longest_substring

## Main
result = {}
for string in ['abcabcbb', 'bbbbb', 'ppwwkew', 'wcabcdeghi', 'bpfbhmipx', 'tmmzuxt', 'AABGAKGIMN', 'stackoverflow']:
    result[string] = lengthOfLongestSubstring(string)
print(result)

Sample run:

{'abcabcbb': 3, 'bbbbb': 1, 'ppwwkew': 3, 'wcabcdeghi': 8, 'bpfbhmipx': 7, 'tmmzuxt': 5, 'AABGAKGIMN': 6, 'stackoverflow': 11}

Upvotes: 3

Related Questions