3. Longest Substring Without Repeating Characters (Medium)

Question

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.

Solution 1: Brute Force (TLE)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        
        ans = 1
        n = len(s)
        for i in range(n - 1):
            for j in range(i + 1, n):
                subS = s[i:j+1]
                if(self.allUnique(subS)):
                    ans = max(ans, j - i + 1)
        return ans
    
    def allUnique(self, subStr):
        subSet = set()
        for i in subStr:
            if i in subSet:
                return False
            else:
                subSet.add(i)
        return True

Time Complexity: O(N^3)
Space Complexity: O(N)

Solution 2: Hash + Slide Window

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = 0
        n = len(s)
        
        lastRepeatIdxofVal = {}
        lftIdx, rhtIdx = 0, 0
        while(rhtIdx < n):
            val = s[rhtIdx]
            
            # Update Left Window
            if val in lastRepeatIdxofVal:
                lftIdx = max(lftIdx, lastRepeatIdxofVal[val] + 1)
            
            lastRepeatIdxofVal[val] = rhtIdx
            ans = max(ans, rhtIdx - lftIdx + 1)
            rhtIdx += 1
        return ans

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Triple Pointer

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        
        ans = 1
        n = len(s)
        lftIdx, rhtIdx = 0, 1
        while(rhtIdx < n):
            for chkIdx in range(lftIdx, rhtIdx):
                if s[chkIdx] == s[rhtIdx]:
                    ans = max(ans, rhtIdx - lftIdx)
                    lftIdx = chkIdx + 1
            rhtIdx += 1
        ans = max(ans, rhtIdx - lftIdx)
        return ans

Time Complexity: O(N^2)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/2580534/100-Best-Solution-Explained
https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/2576799/C%2B%2B-code-without-using-any-space

Follow-up: 159. Longest Substring with At Most Two Distinct Characters

Given a string s , find the length of the longest substring t that contains at most 2 distinct characters.
Example 1:

Input: "eceba"
Output: 3
Explanation: tis "ece" which its length is 3.

Example 2:

Input: "ccaabbb"
Output: 5
Explanation: tis "aabbb" which its length is 5.

TODO

Time Complexity: O(N)
Space Complexity: O(N)

4. Median of Two Sorted Arrays (Hard)

Question

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays

1. The overall run time complexity should be O(log (m+n))

Example 2

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5

Solution 1: Brute Force

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums3 = nums1 + nums2
        nums3.sort()
        
        n = len(nums3)
        # odd
        if n & 1:        
            ans = nums3[n // 2]
        # even
        else:
            ans = (nums3[n // 2 - 1] + nums3[n // 2]) / 2
        
        return ans

Time Complexity: O((M+N)*log(M+N))
Space Complexity: O(M+N)

Solution 2: Optimized Brute Force

Time Complexity: O(M+N)
Space Complexity: O(1)

Solution 3: Binary Search

TODO

Time Complexity: O(log(M+N))
Space Complexity: O(1)

Reference

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2580535/100-Best-Solution-Explained
https://www.geeksforgeeks.org/median-of-two-sorted-arrays-of-different-sizes/

Follow-up: 74. Search a 2D Matrix