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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Amortized analysis

Starter code: class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        

Solutions:
class Solution:

	def lengthOfLongestSubstring(self, s):
		(L, res, last) = (-1, 0, {})
		for (R, char) in enumerate(s):
			if char in last and last[char] > L:
				L = last[char]
			elif R - L > res:
				res = R - L
			last[char] = R
		return res


class Solution:

	def lengthOfLongestSubstring(self, s):
		helper_dict = {}
		longest_start = 0
		longest_end = -1
		current_start = 0
		for (char_index, char) in enumerate(s):
			if char not in helper_dict or helper_dict[char] < current_start:
				helper_dict[char] = char_index
			else:
				current_start = helper_dict[char] + 1
				helper_dict[char] = char_index
			if char_index - current_start > longest_end - longest_start:
				longest_start = current_start
				longest_end = char_index
		return longest_end - longest_start + 1


class Solution:

	def lengthOfLongestSubstring(self, s):
		char_dict = {}
		longest_run = 0
		current_run = 0
		distance = 2
		for (i, char) in enumerate(s):
			if char in char_dict:
				distance = i - char_dict[char]
				if distance <= current_run:
					current_run = distance
				else:
					current_run += 1
			else:
				current_run += 1
			char_dict[char] = i
			if current_run > longest_run:
				longest_run = current_run
		return longest_run


class Solution:

	def lengthOfLongestSubstring(self, s):
		dic = {}
		start = max_len = 0
		for (i, c) in enumerate(s):
			if c in dic and start <= dic[c]:
				start = dic[c] + 1
			else:
				max_len = max(max_len, i - start + 1)
			dic[c] = i
		return max_len


class Solution:

	def lengthOfLongestSubstring(self, s):
		head = 0
		dic = {}
		res = 0
		for i in range(len(s)):
			if s[i] in dic and dic[s[i]] >= head:
				res = max(res, i - head)
				head = dic[s[i]] + 1
			dic[s[i]] = i
		return max(res, len(s) - head)


class Solution:

	def lengthOfLongestSubstring(self, s):
		start = 0
		end = 0
		seen_set = set()
		longest_substring = ''
		while end < len(s):
			end += 1
			currentelem = s[end - 1]
			if currentelem not in seen_set:
				seen_set.add(currentelem)
				if end - start > len(longest_substring):
					longest_substring = s[start:end]
			else:
				while start < end - 1:
					if s[start] != currentelem:
						seen_set.remove(s[start])
						start += 1
					else:
						start += 1
						break
		return len(longest_substring)


class Solution:

	def lengthOfLongestSubstring(self, s):
		record = {}
		result = 0
		start = -1
		for (i, x) in enumerate(s):
			if x in record:
				start = max(start, record[x])
			record[x] = i
			result = max(result, i - start)
		return result


class Solution:

	def lengthOfLongestSubstring(self, s):
		idx = i = 0
		record = set()
		count = 0
		maxcount = 0
		while i < len(s):
			if s[i] in record:
				record.remove(s[idx])
				count -= 1
				idx += 1
			else:
				record.add(s[i])
				count += 1
				i += 1
				if count > maxcount:
					maxcount = count
		return maxcount


class Solution:

	def lengthOfLongestSubstring(self, s):
		result = 0
		if len(s) == 0:
			return result
		hashmap = {}
		start = 0
		for i in range(len(s)):
			if s[i] in hashmap:
				start = max(hashmap[s[i]] + 1, start)
			hashmap[s[i]] = i
			result = max(result, i - start + 1)
		return result