How can I loop through a python list stopping at every element

user_10105186 0
Viewed 44

I am trying to solve this Leetcode problem, without using Sets

https://leetcode.com/problems/longest-substring-without-repeating-characters/

The way im tackling it is by stopping at every element in the list and going one element right until i find a duplicate, store that as the longest subset without duplication and continuing with the next element to do it again.

I'm stuck because i cant find a way to iterate the whole list at every element

Below is what i have so far

def lengthOfLongestSubstring(self, s):
    mylist = list(s)
    mylist2 = list(s)
    final_res = []
    res = []

    for i in mylist2:
        for char in mylist:
            if char in res:
                res=[]
                break
            else:
                res.append(char)
            if len(res) > len(final_res):
                final_res = res
    return final_res
list python
1 Answers

If your goal is primarily to avoid using set (or dict), you can use a solution based on buckets for the full range of possible characters ("English letters, digits, symbols and spaces", which have numeric codes in the range 0-127):

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        '''
        at a given index i with char c, 
            if the value for c in the list of buckets b
            has a value (index of most recent sighting) > start,
                update start to be that value + 1
            otherwise update res to be max(res, i - start + 1)
            update the value for c in b to be i
        '''
        res, start, b = 0, 0, [-1]*128
        for i, c in enumerate(s):
            k = ord(c)
            if b[k] >= start:
                start = b[k] + 1
            else:
                res = max(res, i - start + 1)
            b[k] = i
        return res

The call to ord() allows integer indexing of the bucketed list b.

user_181354540
Related