Problem difficulty: Medium
Problem description
Given a string s, find the length of the longest
substring without repeating characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Solution Approach
To solve this problem we need sliding window technique. First we need to take a look what sliding window is ?
The sliding window technique is a common method used to solve problem involving arrays or strings where you need to find a subset of element that satisfy certain conditions. This technique reduce time complexity from O(n^2) to O(n).
Steps of sliding window technique
- Initialize the window: Use two pointer left and right to define the boundary of window and it all start from beginning of the array or string.
- Expand the window: Once the window violate move left pointer forward until the window is satisfied again.
- Update the result: During the process update the result, max length, or sum …
- Repeat: Repeat until the right pointer reaches the end of the array
For solving this problem above we have three differences solution for it
Solution 1: Using Set to store unique substring
- Use `charSet` to store the unique substring
- Initialize left, right pointer and iterate through the array
- `maxLength` to keep track the the length of longest substring
- if character in `charSet` which mean its violated the rule so we move left forward and remove char from `charSet` and if character not in charSet which mean not violate, we calculate maxLength and add character to charSet
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
maxLenght, left = 0, 0
charSet = set()
for right, char in enumerate(s):
if char in charSet:
while s[left] in charSet:
charSet.remove(s[left])
left += 1
else:
charSet.add(char)
maxLenght = max(maxLenght, right - left + 1)
return maxLenght
Solution 2: Instead of store character in charSet we can store in hashTable with key is current character and value is index of it
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
maxLenght, left = 0, 0
mapChar = {}
for right, char in enumerate(s):
if char in mapChar:
left = mapChar[char] + 1
else:
maxLenght = max(maxLenght, right - left + 1)
mapChar[char] = right
return maxLenght
Solution 3: This solution is the same as solution 2, instead of store in hashTable we can store in array with the index is the ASCII number of that character
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
maxLenght, left = 0, 0
arrayChar = [-1] * 128 # init array with size 128 with each item equal to -1
for right, char in enumerate(s):
if arrayChar[ord(char)] >= left:
left = arrayChar[ord(char)] + 1
else:
maxLenght = max(maxLenght, right - left + 1)
arrayChar[ord(char)] = right
return maxLenght
Source code : https://github.com/hongquan080799/leetcode/tree/master/length_of_longest_substring
