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

CodePudding user response：

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.

CodePudding user response：

i used hash table and it's O(1):

def longest(mystring):
    numbers = {ord(x): 0 for x in mystring}
    left = right = 0

    for number in mystring:
        number = ord(number)
        if numbers[number] == 0:
            left_count = number - 1
            right_count = number    1

            while left_count in numbers:
                numbers[left_count] == 1
                left_count -= 1
            left_count  = 1

            while right_count in numbers:
                numbers[right_count] == 1
                right_count  = 1
            right_count -= 1

            if (right - left) <= (right_count-left_count):
                right = right_count
                left = left_count

    longest = ""
    for i in range(left,right 1):
        longest =(chr(i))

    answer = f"The answer is '{longest}', with the length of {right - left   1}."
    return answer 

INPUT

mystring = ["x","b","c","d","e","h","s","z","l","m","n"]

or

mystring = "xbcdehszlmn"

OUTPUT

"The answer is 'bcde', with the length of 4."