Press "Enter" to skip to content

Posts tagged as “sliding window”

花花酱 LeetCode 1208. Get Equal Substrings Within Budget

You are given two strings s and t of the same length. You want to change s to t. Changing the i-th character of s to i-th character of t costs |s[i] - t[i]| that is, the absolute difference between the ASCII values of the characters.

You are also given an integer maxCost.

Return the maximum length of a substring of s that can be changed to be the same as the corresponding substring of twith a cost less than or equal to maxCost.

If there is no substring from s that can be changed to its corresponding substring from t, return 0.

Example 1:

Input: s = "abcd", t = "bcdf", cost = 3
Output: 3
Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.

Example 2:

Input: s = "abcd", t = "cdef", cost = 3
Output: 1
Explanation: Each charactor in s costs 2 to change to charactor in t, so the maximum length is 1.

Example 3:

Input: s = "abcd", t = "acde", cost = 0
Output: 1
Explanation: You can't make any change, so the maximum length is 1.

Constraints:

  • 1 <= s.length, t.length <= 10^5
  • 0 <= maxCost <= 10^6
  • s and t only contain lower case English letters.

Solution 1: Binary Search

Time complexity: O(nlogn)
Space complexity: O(n)

C++

Solution 2: Sliding Window

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1176. Diet Plan Performance

A dieter consumes calories[i] calories on the i-th day.  For every consecutive sequence of k days, they look at T, the total calories consumed during that sequence of k days:

  • If T < lower, they performed poorly on their diet and lose 1 point; 
  • If T > upper, they performed well on their diet and gain 1 point;
  • Otherwise, they performed normally and there is no change in points.

Return the total number of points the dieter has after all calories.length days.

Note that: The total points could be negative.

Example 1:

Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explaination: calories[0], calories[1] < lower and calories[3], calories[4] > upper, total points = 0.

Example 2:

Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explaination: calories[0] + calories[1] > upper, total points = 1.

Example 3:

Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explaination: calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, total points = 0.

Constraints:

  • 1 <= k <= calories.length <= 10^5
  • 0 <= calories[i] <= 20000
  • 0 <= lower <= upper

Solution: Sliding Window

Maintain the sum of a sliding window length of k.

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1052. Grumpy Bookstore Owner

Today, the bookstore owner has a store open for customers.length minutes.  Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy.  If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0.  When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

  • 1 <= X <= customers.length == grumpy.length <= 20000
  • 0 <= customers[i] <= 1000
  • 0 <= grumpy[i] <= 1

Solution: Sliding Window

Sum the costumers of non grumpy minutes, recording the max sum of the sliding window of size X.

Time complexity: O(n)
Space complexity: o(n)

C++

花花酱 LeetCode 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguoussubarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n). 

Solution 1: Two Pointers (Sliding Window)

Maintain a sliding window [l, r) such that sum(nums[l:r)) >= s, then move l to l + 1, and move r accordingly to make the window valid.

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 1004. Max Consecutive Ones III

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s. 

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Note:

  1. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. A[i] is 0 or 1 

Solution : Sliding Window

Maintain a window that has at most K zeros

Time complexity: O(n)
Space complexity: O(1)

C++