Shortest Sub{string,array}

Usually, both expansion and shrinking will be having while loop, and condition for shrink will just be the complement/negation/opposite of expansion.

Naïve

while expand + while shrink

209. Minimum Size Subarray Sum (Medium)

Solution

The problem involves finding the minimum length of a contiguous subarray of which the sum is greater than or equal to a given target. The solution employs a sliding window approach to dynamically adjust the subarray being considered, expanding to increase the total sum and shrinking to seek the minimal length meeting the sum requirement.

The expansion phase extends the window to include more elements until the subarray’s total sum meets or exceeds the target. However, this initial subarray may not represent the minimal length capable of achieving the target sum, necessitating a shrinking phase.

Expansion:

• Expand the window by incrementing the right pointer, adding to total until it reaches or surpasses the target sum.

• But this subarray might not be the minimum subarray, since it can be trimmed from the left to make it even more smaller subarray but with sum greater than or equal to the subarray.

Shrinking:

• Once the target is met, shrink the window from the left to potentially reduce its size while still meeting or exceeding the target sum. The problem logic, focused on identifying the minimum subarray length, is integrated within this phase, before adjusting total and left.

• Note its total >= target and not total > target, the latter will lead to an infinite loop.

Logic:

• Within the shrinking phase, before decrementing total or incrementing left, calculate and update mini to reflect the shortest subarray length found that meets the sum requirement.

The function minSubArrayLen returns mini if a valid subarray is found; otherwise, it returns 0, indicating no such subarray exists within nums.

Analysis

Time Complexity: O(N)

• The algorithm iterates through nums once with a sliding window, adjusting its size as necessary. Each element is added to the window exactly once during expansion and removed at most once during shrinking, ensuring linear time complexity.

Space Complexity: O(1)

• Constant space is utilized, as the solution employs a minimal number of variables (left, right, total, mini) to manage the window’s boundaries and compute the minimal subarray length.

Python

def minSubArrayLen(self, target: int, nums: List[int]) -> int:
    n = len(nums)
    left = right = 0
    total = 0
    mini = float("inf")
    while right < n:
        # Expansion
        while right < n and total < target:
            total += nums[right]
            right += 1
        # Shrinking
        while left < right and total >= target:
            # Logic
            mini = min(mini, right - left)
            total -= nums[left]
            left += 1

    return mini if mini != float("inf") else 0

2260. Minimum Consecutive Cards to Pick Up (Medium)

Solution

The challenge is to find the minimum number of consecutive cards needed to pick up at least one pair of matching cards from a given array cards. This problem is approached using a sliding window technique, complemented by a counter to track the frequency of each card within the current window.

The solution iterates through cards, dynamically adjusting the window to capture the shortest sequence containing a pair of matching cards. The counter aids in monitoring each card’s presence within the window, facilitating the identification of a valid pair.

Expansion:

• The window expands by moving the right pointer forward, incrementing the counter for the current card. Expansion continues until a paired card (a duplicate) is encountered within the window, as indicated by the paired lambda function.

Logic:

• Upon detecting a pair within the window, calculate the current window’s length (right - left) and update mini if this length represents a shorter sequence than previously recorded.

Shrinking:

• To find potentially smaller valid sequences, the window shrinks from the left by decrementing the left pointer, adjusting the counter accordingly. This process continues until the paired condition is no longer met, ensuring every possible sequence is evaluated for its length.

The function minimumCardPickup returns mini if a valid sequence is found, indicating the minimum number of consecutive cards required to pick up a pair; otherwise, it returns -1 if no pairs exist in cards.

Analysis

Time Complexity: O(N)

• The algorithm iterates through the array cards once with a sliding window, adjusting its size as necessary. Each card is considered exactly once for inclusion and possible removal from the window, ensuring linear time complexity.

Space Complexity: O(N)

• The space complexity is determined by the size of the counter, which tracks the frequency of cards within the window. In the worst case, the counter could contain an entry for every unique card in cards, indicating the space requirement is proportional to the number of unique cards.

Python

def minimumCardPickup(self, cards: List[int]) -> int:
    n = len(cards)
    left = right = 0
    counter = collections.Counter()
    mini = float("inf")

    # Lambda function to check if the current window contains a pair
    paired = lambda: counter.get(cards[right - 1], 0) > 1

    while right < n:
        while right < n and not paired():
            counter[cards[right]] += 1
            right += 1
        while left < right and paired():
            mini = min(mini, right - left)
            counter[cards[left]] -= 1
            left += 1
    return mini if mini != float("inf") else -1

---

Two strings

while expand + while shrink

76. Minimum Window Substring (Hard)

Solution

The objective is to find the smallest window in the string s that contains all the characters of the string t. The solution employs a sliding window approach along with two hashmaps to track the frequency of characters required by t and those currently in the window of s.

Consider s: “ABAACBAB” and t: “ABC”. The shortest window containing all characters of t is “ACB” with indices (5, 6, 7).

• Image illustration of the process:

  

• Cache all frequencies required by t in a hashmap required_counter.

• Track frequencies of all characters in any subarray of s using counter, and maintain the count of required unique characters as required.

Expansion:

• Expand the window until all required characters are included or required == 0, updating counter for s[right]. Decrement required when a character’s frequency in counter matches its required frequency in required_counter.

Shrinking:

• Shrink the window while ensuring the requirement for all elements still holds (required == 0). Increment required when a necessary character is removed, indicating the window no longer contains all characters from t.

Problem Logic:

• The logic for determining the minimum window is applied during the shrinking phase, capturing the left and right pointers for the smallest valid window encountered.

Analysis

Time Complexity: O(M + N)

• The complexity considers the lengths of both s (M) and t (N), accounting for the initial population of required_counter and the single pass through s with potential revisits during window adjustments.

Space Complexity: O(2 * 26)

• The space requirement stems from storing character frequencies in required_counter and counter, each potentially containing every unique character [A - Z] from s and t. Counters’ size is bounded by the character set size, not the string lengths.

Python

def minWindow(self, s: str, t: str) -> str:
    n = len(s)
    left = right = 0
    required_counter = collections.Counter(t)
    counter = collections.Counter()
    required = len(required_counter)  # no of unique elements
    mini = (0, float("inf"))  # (left, right)

    contains = lambda: required == 0
    req_char_satisfied = lambda i: counter[s[i]] == required_counter.get(s[i], 0)
    req_char_removed = lambda i: counter[s[i]] < required_counter.get(s[i], 0)

    while right < n:
        # Expansion
        while right < n and not contains():
            counter[s[right]] += 1
            if req_char_satisfied(right):
                required -= 1
            right += 1
        # Shrinking
        while left < right and contains():
            # Logic
            mini = min(mini, (left, right), key=lambda i: i[1] - i[0])
            counter[s[left]] -= 1
            if req_char_removed(left):
                required += 1
            left += 1

    return s[slice(*mini)] if mini != (0, float("inf")) else ""

Smallest window containing 0, 1 and 2 (Easy)

Solution

A special case of 76. Minimum Window Substring (Hard), where t = "012".

The challenge is to identify the shortest substring within s that includes all digits “0”, “1”, and “2” at least once. A sliding window approach is employed, utilizing a counter to track the frequency of each required digit within the current window and dynamically adjusting the window to encapsulate a valid substring.

Important

A crucial optimization in this solution is the early return statement. Given that the minimum length of a valid substring is 3 (as each required character must appear at least once), the solution can terminate early if such a substring is found, significantly reducing the time complexity in cases where early matches occur. This is particularly effective in addressing Time Limit Exceeded (TLE) issues by avoiding unnecessary iterations over the remainder of the string once the optimal solution is identified.

Expansion:

• The window expands by incrementing the right pointer, updating the counter for each character included. If a character satisfies its requirement (matching the frequency in required_counter), decrement required.

Shrinking:

• Once all required characters are present, the window attempts to shrink from the left, updating mini with the current window size if it’s smaller than previously recorded. Crucially, if a window of length 3 is found, the function immediately returns 3, leveraging the early return optimization.

Logic:

• The early return when mini[1] - mini[0] == 3 directly follows the recognition of a valid substring, ensuring minimal processing time by promptly concluding the search upon finding the most efficient solution.

The function returns the length of the smallest valid substring if found; otherwise, it returns -1 if no such substring exists within s.

Analysis

Time Complexity: O(N)

• Despite the linear pass through s, the early return optimization ensures that the solution ceases execution as soon as a minimal-length substring is identified, potentially reducing the effective number of iterations significantly.

Space Complexity: O(1)

• The space complexity remains constant, with counter and required_counter limited by the small, fixed set of characters of interest (“0”, “1”, “2”), and a few variables managing the window’s boundaries and state.

Python

def smallestSubstring(self, s):
    n = len(s)
    left = right = 0
    required_counter = {i: 1 for i in "012"}
    counter = collections.Counter()
    required = len(required_counter)  # no of unique elements
    mini = (0, float("inf"))  # (left, right)

    contains = lambda: required == 0
    req_char_satisfied = lambda i: counter[s[i]] == required_counter.get(s[i], 0)
    req_char_removed = lambda i: counter[s[i]] < required_counter.get(s[i], 0)

    while right < n:
        # Expansion
        while right < n and not contains():
            counter[s[right]] += 1
            if req_char_satisfied(right):
                required -= 1
            right += 1
        # Shrinking
        while left < right and contains():
            # Logic
            mini = min(mini, (left, right), key=lambda i: i[1] - i[0])
            if mini[1] - mini[0] == 3:  # 3 is the most minimum length
                return 3
            counter[s[left]] -= 1
            if req_char_removed(left):
                required += 1
            left += 1

    return mini[1] - mini[0] if mini != (0, float("inf")) else -1