[LeetCode] 594. Longest Harmonious Subsequence

Problem : https://leetcode.com/problems/longest-harmonious-subsequence/description/

Since we only need the length of the subsequence, we don't need to preserve the original order of the numbers. We can sort the origin array in non-decreasing order and use sliding window to find the longest subsequence.

The left pointer points to the minmum value and the right pointer points to the maximum value.

Move left pointer to right, when the difference is larger than 1.

Move right pointer to right, when the difference is smaller or equal to 1.

Update the longest subsequence length when the difference is equal to 1.

class Solution {
    public int findLHS(int[] nums) {
        Arrays.sort(nums);

        int left = 0; 
        int result = 0;
        for (int right = 0; right < nums.length;) {
            long diff = nums[right] - nums[left];
            if (diff < 1L) {
                right++;
                continue;
            }
            if (diff == 1L) {
                result = Math.max(result, right - left + 1);
                right++;
                continue;
            }
            left += 1;
        }
        
        return result;
    }

[LeetCode] 904. Fruit Into Baskets

 Problem : https://leetcode.com/problems/fruit-into-baskets/

Use sliding window approach to find the maximum contiguous section contains 2 unique numbers.

Time complexity = O ( N ), N = len(fruits).

Because for each number, it will either be added to the window or removed from the window once.

class Solution {
    public int totalFruit(int[] fruits) {
        int[] counter = new int[fruits.length];
        int uniqNum = 0;

        int result = 0;

        int left = 0;
        for (int right = 0; right < fruits.length; right++) {
            counter[fruits[right]] += 1;
            if (counter[fruits[right]] == 1) {
                uniqNum += 1;
            }

            while (left <= right && uniqNum > 2) {
                counter[fruits[left]] -= 1;
                if (counter[fruits[left]]  == 0) {
                    uniqNum -= 1;
                }
                left += 1;
            }

            result = Math.max(result, right - left + 1);
        }

        return result;
    }
}

[LeetCode] 438. Find All Anagrams in a String

 Problem : https://leetcode.com/problems/find-all-anagrams-in-a-string/

Use sliding window approach. 

Time complexity =  O (M) + O (N). M = length of s. N = length of p.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        Map<Character, Integer> counter = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            counter.put(p.charAt(i), counter.getOrDefault(p.charAt(i), 0) + 1);
        }
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            counter.put(s.charAt(right), counter.getOrDefault(s.charAt(right), 0) - 1);
            while(left <= right && counter.get(s.charAt(right)) < 0) {
                counter.put(s.charAt(left), counter.get(s.charAt(left)) + 1);
                left += 1;
            }

            if (right + 1 - left == p.length()) {
                result.add(left);
            }
        }

        return result;
    }
}

Updated on 02/05/2023. Updated for a simplier sliding window solution which uses one hashmap to record the enoutered needed letters.

[LeetCode] 159. Longest Substring with At Most Two Distinct Characters

 Problem :  https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

This is a classic sliding window problem.

class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        seen = defaultdict(int)
        distinct = 0
        result = 0
        
        right = 0
        
        for left in range(len(s)):
            while right < len(s) and distinct <= 2:
                seen[s[right]] += 1
                
                if seen[s[right]] == 1:
                    distinct += 1
                
                right += 1
                
                if distinct <= 2:
                    result = max(result, right - left)
             
            seen[s[left]] -= 1
            if seen[s[left]] == 0:
                distinct -= 1
                
        return result

[LeetCode] 209. Minimum Size Subarray Sum

 Problem : https://leetcode.com/problems/minimum-size-subarray-sum/

Sliding-window approach.

Time Complexity = O ( N )

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        MAX_INT = 2 ** 31 - 1
        result = MAX_INT
        right = 0
        sums = 0
        
        for left in range(len(nums)):
            while right < len(nums) and sums < s:
                sums += nums[right]
                right += 1
            
            if sums >= s:
                result = min(result, right - left)
            
            sums -= nums[left]
        
        return result if result != MAX_INT else 0

[LeetCode] 82. Remove Duplicates from Sorted List II

Problem : https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

Traverse the origin linked list and count the visited numbers.  Then append distinct number to the output linked list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        
        dummy = ListNode(0)
        p1 = dummy
        
        p2 = head
        count = 1
        
        while p2 and p2.next:
            if p2.val == p2.next.val:
                count += 1
                p2 = p2.next
            else:
                if count == 1:
                    p1.next = p2
                    p1 = p1.next
                
                count = 1
                p2 = p2.next
    
        if p2 and count == 1:
            p1.next = p2
            p1 = p1.next
        
        # end the output linked list
        p1.next = None
        
        return dummy.next

A Sliding-window solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        p = head
        q = head
        
        dummy = ListNode()
        n = dummy
        
        while p:
            while q and p.val == q.val:
                q = q.next
            
            if p.next == q:
                n.next = p
                n = n.next
            
            p = q
            
        # end the new list
        n.next = None
            
        return dummy.next

[LeetCode] 76. Minimum Window Substring

Problem : https://leetcode.com/problems/minimum-window-substring/

Use sliding window based approach. Firstly expand window to find the longest substring contains all characters of target string. Then shrink window to find the valid shortest substring.

Time Complexity : O ( S + T ) 

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        counter = Counter(t)
        
        right = 0
        seen = defaultdict(int)
        count = 0
        
        windowStart = -1
        windowSize = 2 ** 31 - 1
        
        for left in range(len(s)):
            while right < len(s) and count < len(counter):
                seen[s[right]] += 1
                
                if seen[s[right]] == counter[s[right]]:
                    count += 1
                
                right += 1
            
            if count == len(counter):
                if windowSize > right - left:
                    windowStart = left
                    windowSize = right - left
            
            seen[s[left]] -= 1
            if seen[s[left]] == counter[s[left]] - 1:
                count -= 1
            
        
        if windowStart == -1: 
            return ""
        
        return s[windowStart:windowStart + windowSize]
                

[LeetCode] 3. Longest Substring Without Repeating Characters

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

Use hash map to save the index of visited character.
For every character, locate the last position of this character in the hash map.

If found and the last character is inside of current substring, restart the substring after the duplicated character's last position.

Otherwise, increase current substring length.

Time Complexity = O( N ), N = len(s)
Space Complexity = O( N ), for the space used by the hash map.

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = defaultdict(lambda: -1)

        left = -1
        result = 0

        for right, letter in enumerate(s):
            left = max(seen[letter], left)  # shrink window if needed

            result = max(result, right - left)
            seen[letter] = right # remember the last position the letter was seen
            
        return result

A classical sliding window implementation. Count encoutered letter with hash table.

Time complexity = O ( 2 * N ), N = len(s)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> counter = new HashMap<>();
        int left = 0;
        int result = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char rc = s.charAt(right);
            counter.put(rc, counter.getOrDefault(rc, 0) + 1);
            
            while (counter.get(rc) > 1) {
                char lc = s.charAt(left);
                counter.put(lc, counter.get(lc) - 1);
                left += 1;
            }
            
            result = Math.max(result, right - left + 1);
        }
        
        return result;
    }
}

Edited on 06/10/2022. Replaced with the Java version sliding window approach.

Edited on 06/16/2021. Added the Python version sliding window approach.