Press "Enter" to skip to content

Posts published in “Sliding Window”

花花酱 LeetCode 1525. Number of Good Ways to Split a String

You are given a string s, a split is called good if you can split s into 2 non-empty strings p and q where its concatenation is equal to s and the number of distinct letters in p and q are the same.

Return the number of good splits you can make in s.

Example 1:

Input: s = "aacaba"
Output: 2
Explanation: There are 5 ways to split "aacaba" and 2 of them are good. 
("a", "acaba") Left string and right string contains 1 and 3 different letters respectively.
("aa", "caba") Left string and right string contains 1 and 3 different letters respectively.
("aac", "aba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aaca", "ba") Left string and right string contains 2 and 2 different letters respectively (good split).
("aacab", "a") Left string and right string contains 3 and 1 different letters respectively.

Example 2:

Input: s = "abcd"
Output: 1
Explanation: Split the string as follows ("ab", "cd").

Example 3:

Input: s = "aaaaa"
Output: 4
Explanation: All possible splits are good.

Example 4:

Input: s = "acbadbaada"
Output: 2

Constraints:

  • s contains only lowercase English letters.
  • 1 <= s.length <= 10^5

Solution: Sliding Window

  1. Count the frequency of each letter and count number of unique letters for the entire string as right part.
  2. Iterate over the string, add current letter to the left part, and remove it from the right part.
  3. We only
    1. increase the number of unique letters when its frequency becomes to 1
    2. decrease the number of unique letters when its frequency becomes to 0

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

C++

java

Python3

花花酱 LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:

Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:

Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 1000
  • 1 <= target <= 10^8

Solution: Sliding Window + Best so far

  1. Use a sliding window to maintain a subarray whose sum is <= target
  2. When the sum of the sliding window equals to target, we found a subarray [s, e]
  3. Update ans with it’s length + shortest subarray which ends before s.
  4. We can use an array to store the shortest subarray which ends before s.

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

C++

花花酱 LeetCode 1456. Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k.

Return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are (a, e, i, o, u).

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Example 4:

Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.

Example 5:

Input: s = "tryhard", k = 4
Output: 1

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
  • 1 <= k <= s.length

Solution: Sliding Window

Keep tracking the number of vows in a window of size k.

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

C++

花花酱 LeetCode 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

Given an array of integers arr and two integers k and threshold.

Return the number of sub-arrays of size k and average greater than or equal to threshold.

Example 1:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:

Input: arr = [1,1,1,1,1], k = 1, threshold = 0
Output: 5

Example 3:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Example 4:

Input: arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
Output: 1

Example 5:

Input: arr = [4,4,4,4], k = 4, threshold = 1
Output: 1

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^4
  • 1 <= k <= arr.length
  • 0 <= threshold <= 10^4

Solution: Sliding Window

  1. Window size = k
  2. Maintain the sum of the window
  3. Check sum >= threshold * k

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

C++

花花酱 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++