209. Minimum Size Subarray Sum
Problem
Given an array of n positive integers and a positive integer target.
Find the subarray [numsl, numsl+1, …, numsr-1, numsr] in the array whose sum is greater than or equal to target and that has the smallest length, and return its length. If no such subarray exists, return 0.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] is the smallest-length subarray under this condition.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
Approach
Use the two-pointer variable-length sliding window idea.
Set a left pointer to control the window size, and use the array index from the loop as the right pointer.
Set a variable that tracks the sum of the numbers in the window.
When the sum meets the requirement:
- Use a while loop
- Update the minimum length of the subarray
- Exclude the value on the left from the window, update the sum, and move the left pointer to the right at the same time
- End the loop when the sum no longer meets the requirement
Solution
// 209.长度最小的子数组
package main
import (
"fmt"
"math"
)
func minSubArrayLen(target int, nums []int) int {
ans, left := math.MaxInt, 0
cnt := 0
for i, num := range nums {
cnt += num
for cnt >= target {
ans = min(ans, i-left+1)
cnt -= nums[left]
left += 1
}
}
if ans > len(nums) {
return 0
} else {
return ans
}
}
func main() {
testCases := []struct {
nums []int
target int
}{
{[]int{2, 3, 1, 2, 4, 3}, 7},
{[]int{1, 4, 4}, 4},
{[]int{1, 1, 1, 1, 1, 1, 1, 1}, 11},
}
for _, testCase := range testCases {
fmt.Println(minSubArrayLen(testCase.target, testCase.nums))
}
}
2904. Shortest and Lexicographically Smallest Beautiful String
Problem
You are given a binary string s and a positive integer k.
If the number of 1s in some substring of s is exactly equal to k, then this substring is called a beautiful substring.
Let len be the length of the shortest beautiful substring.
Return the beautiful substring of length len that is lexicographically smallest. If s contains no beautiful substring, return an empty string.
For two strings a and b of the same length, string a is considered lexicographically greater than string b if at the first position where a and b differ, the character in a at that position is strictly greater than the corresponding character in b.
For example, “abcd” is lexicographically greater than “abcc”, because the first position where the two strings differ is the fourth character, and d is greater than c.
Example 1:
Input: s = “100011001”, k = 3
Output: “11001”
Explanation: There are 7 beautiful substrings in the example:
- The substring “100011001”.
- The substring “100011001”.
- The substring “100011001”.
- The substring “100011001”.
- The substring “100011001”.
- The substring “100011001”.
- The substring “100011001”.
The length of the shortest beautiful substring is 5.
The beautiful substring of length 5 that is lexicographically smallest is the substring “11001”.
Example 2:
Input: s = “1011”, k = 2
Output: “11”
Explanation: There are 3 beautiful substrings in the example:
- The substring “1011”.
- The substring “1011”.
- The substring “1011”.
The length of the shortest beautiful substring is 2.
The beautiful substring of length 2 that is lexicographically smallest is the substring “11”.
Example 3:
Input: s = “000”, k = 1
Output: ""
Explanation: There is no beautiful substring in the example.
Constraints:
1 <= s.length <= 100
1 <= k <= s.length
Approach
What we need to do is find a substring in which the number of 1s is k; if there are multiple answers, return the one that is lexicographically smallest.
First, according to the problem, when the number of 1s in the string is less than k, an empty string is returned, so return it directly.
Then initialize the result ans to the input string s, because the worst result is s, so set it to s.
After that, set cnt to the number of 1s in the window and left to the left boundary of the window, and use the loop index as the right boundary.
Each time the right boundary moves:
- Check whether the number of 1s in the window meets the requirement
- If it does, start moving the left boundary until the leftmost 1 is excluded
- In this process there may be many 0s on the left; excluding them shortens the substring, so keep updating the substring and the left boundary, and also pay attention to the case where substrings have the same length, where the lexicographically smallest one must be chosen
- This process is implemented with a while loop
Solution
// 2904.最短且字典序最小的美丽子字符串
package main
import (
"fmt"
"strings"
)
func shortestBeautifulSubstring(s string, k int) string {
if strings.Count(s, "1") < k {
return ""
}
ans := s
cnt, left := 0, 0
for i, ch := range s {
if ch == '1' {
cnt += 1
}
for cnt >= k {
tmp := s[left : i+1]
if s[left] == '1' {
cnt -= 1
}
left += 1
if len(tmp) == len(ans) {
if tmp < ans {
ans = tmp
}
}
if len(tmp) < len(ans) {
ans = tmp
}
}
}
return ans
}
func main() {
testCases := []struct {
s string
k int
}{
{"100011001", 3},
{"1011", 2},
{"000", 1},
}
for _, testCase := range testCases {
fmt.Println(shortestBeautifulSubstring(testCase.s, testCase.k))
}
}
1234. Replace the Substring for Balanced String
Problem
There is a string of length n that contains only the four characters ‘Q’, ‘W’, ‘E’, and ‘R’.
If in this string these four characters each occur exactly n/4 times, then it is a “balanced string”.
Given such a string s, please make the original string s a “balanced string” by “replacing one substring”.
You may use any other string of the same length as the “substring to be replaced” to perform the replacement.
Please return the minimum possible length of the substring to be replaced.
If the original string is itself a balanced string, return 0.
Example 1:
Input: s = “QWER”
Output: 0
Explanation: s is already balanced.
Example 2:
Input: s = “QQWE”
Output: 1
Explanation: We need to replace one ‘Q’ with ‘R’, so that the resulting “RQWE” (or “QRWE”) is balanced.
Example 3:
Input: s = “QQQW”
Output: 2
Explanation: We can replace the leading “QQ” with “ER”.
Example 4:
Input: s = “QQQQ”
Output: 3
Explanation: We can replace the last 3 ‘Q’s so that s = “QWER”.
Constraints:
1 <= s.length <= 10^5
s.length is a multiple of 4
s contains only the four characters ‘Q’, ‘W’, ‘E’, ‘R’
Approach
Build a minimum window such that the count of each character outside the window is as close to n as possible; this minimum window is the string that needs to be replaced.
Use a hash map to count the number of each character.
Solution
// 1234.替换子串得到平衡字符串
package main
import "fmt"
func balancedString(s string) int {
// 构建哈希表，统计各自的数量
// 构建一个最小窗口，让窗口外的每种字符数量尽量接近n，这个最小窗口就是需要替换的字符串
mp := make(map[byte]int, 4)
n := len(s) / 4
for i := 0; i < len(s); i++ {
mp[s[i]] += 1
}
// 已经平衡，返回0
if mp['Q'] == n && mp['W'] == n && mp['E'] == n && mp['R'] == n {
return 0
}
ans, left := len(s), 0
for i := 0; i < len(s); i++ {
mp[s[i]] -= 1 // 放进窗口
for mp['Q'] <= n && mp['W'] <= n && mp['E'] <= n && mp['R'] <= n {
// 满足条件，记录并收缩
ans = min(ans, i-left+1)
mp[s[left]] += 1
left += 1
}
}
return ans
}
func main() {
testCases := []string{
"QWER",
"QQWE",
"QQQW",
"QQQQ",
}
for _, testCase := range testCases {
fmt.Println(balancedString(testCase))
}
}
2875. Minimum Size Subarray in Infinite Array
Problem
You are given a 0-indexed array nums and an integer target.
The 0-indexed array infinite_nums is generated by infinitely appending the elements of nums to itself.
Find the shortest subarray of infinite_nums whose element sum equals target, and return the length of that subarray. If no subarray satisfying the condition exists, return -1.
Example 1:
Input: nums = [1,2,3], target = 5
Output: 2
Explanation: In this example, infinite_nums = [1,2,3,1,2,3,1,2,…].
The subarray within the interval [1,2] has an element sum equal to target = 5, and the length is 2.
It can be shown that when the element sum equals the target value target = 5, 2 is the shortest length of a subarray.
Example 2:
Input: nums = [1,1,1,2,3], target = 4
Output: 2
Explanation: In this example, infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,…].
The subarray within the interval [4,5] has an element sum equal to target = 4, and the length is 2.
It can be shown that when the element sum equals the target value target = 4, 2 is the shortest length of a subarray.
Example 3:
Input: nums = [2,4,6,8], target = 3
Output: -1
Explanation: In this example, infinite_nums = [2,4,6,8,2,4,6,8,…].
It can be shown that there is no subarray whose element sum equals the target value target = 3.
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
1 <= target <= 10^9
Approach
The number of nums used is not fixed; it may be 1 to n, but it can be observed that if n are used, the middle n-2 are complete, and for the left nums and right nums, we take consecutive data from the right and from the left respectively.
Let the sum of the data in nums be total.
target = total*m + res
res = nums*2[i:j]
What we need to do is find the length of res.
res = target & total
Everything else can be done following the same fixed steps.
Solution
// 2875.无限数组的最短子数组
package main
import (
"fmt"
"math"
)
func minSizeSubarray(nums []int, target int) int {
total := 0
for _, x := range nums {
total += x
}
ans := math.MaxInt
left, sum, n := 0, 0, len(nums)
for right := 0; right < n*2; right++ {
sum += nums[right%n]
for sum > target%total {
sum -= nums[left%n]
left++
}
if sum == target%total {
ans = min(ans, right-left+1)
}
}
if ans == math.MaxInt {
return -1
}
return ans + target/total*n
}
func main() {
testCases := []struct {
nums []int
target int
}{
{[]int{1, 2, 3}, 5},
{[]int{1, 1, 1, 2, 3}, 4},
{[]int{2, 4, 6, 8}, 3},
}
for _, testCase := range testCases {
fmt.Println(minSizeSubarray(testCase.nums, testCase.target))
}
}
76. Minimum Window Substring
Problem
Given a string s and a string t, return the minimum substring of s that covers all the characters of t. If there is no substring in s that covers all the characters of t, return the empty string "".
Note:
For duplicate characters in t, the number of that character in the substring we are looking for must be no less than the number of that character in t.
If such a substring exists in s, we guarantee that it is the only answer.
Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum covering substring “BANC” contains ‘A’, ‘B’, and ‘C’ from string t.
Example 2:
Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum covering substring.
Example 3:
Input: s = “a”, t = “aa”
Output: ""
Explanation: Both characters ‘a’ in t should be included in a substring of s, so there is no substring satisfying the condition, and the empty string is returned.
Constraints:
m == s.length
n == t.length
1 <= m, n <= 10^5
s and t consist of English letters.
Approach
First, the problem asks us to find a substring of s that contains all the characters in t (both the distinct characters and their counts).
First, we need to know which characters are in t.
Then, find a substring in s that contains all kinds of characters in t, and make this substring as small as possible.
So use a hash map to count all the kinds and counts of characters in t.
Then look for a substring in s: if a character in the substring is in the hash map, subtract it; if all the counts in the hash map become 0, it means the substring already contains all the characters in t, then shrink the window until it no longer meets the requirement.
Solution
// 76.最小覆盖子串
package main
import (
"fmt"
"math"
)
func minWindow(s string, t string) string {
// 先统计一下t中各个字符的数量,统计一下字符的种类
mp := make(map[byte]int)
for i := 0; i < len(t); i++ {
mp[t[i]] += 1
}
left := 0
cnt := len(mp) // 字符的种类
ans := ""
tmp := math.MaxInt
for i := 0; i < len(s); i++ {
if _, ok := mp[s[i]]; ok { // 字符有效
mp[s[i]] -= 1
if mp[s[i]] == 0 { // 符合要求
cnt -= 1
}
}
for cnt == 0 { // 子串中已经满足要求，缩小子串范围
if tmp > i-left+1 {
tmp = i - left + 1
ans = s[left : i+1]
}
if _, ok := mp[s[left]]; ok { // 字符有效
mp[s[left]] += 1
if mp[s[left]] == 1 { // 符合要求
cnt += 1
}
}
left += 1
}
}
return ans
}
func main() {
testCases := []struct {
s string
t string
}{
{"ADOBECODEBANC", "ABC"},
{"a", "a"},
{"a", "aa"},
}
for _, testCase := range testCases {
fmt.Println(minWindow(testCase.s, testCase.t))
}
}
632. Smallest Range Covering Elements from K Lists
Problem
You have k lists of integers sorted in non-decreasing order. Find the smallest range such that each of the k lists has at least one number contained in it.
We define range [a,b] as smaller than range [c,d] if b-a < d-c, or if b-a == d-c then a < c.
Example 1:
Input: nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24, 26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
Example 2:
Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]
Constraints:
nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 10^5
nums[i] is sorted in non-decreasing order
Approach
Build pairs containing the number and its position, then sort them, and build a sliding window that covers all indices and is as small as possible.
Solution
// 632.最小区间
package main
import (
"fmt"
"slices"
)
func smallestRange(nums [][]int) []int {
type pair struct{ x, i int } // 数字和他们所在的位置
pairs := []pair{}
for i, arr := range nums {
for _, num := range arr {
pairs = append(pairs, pair{num, i})
}
}
slices.SortFunc(pairs, func(a, b pair) int { return a.x - b.x })
ansL, ansR := pairs[0].x, pairs[len(pairs)-1].x
mp := make(map[int]int)
left := 0
for _, p := range pairs {
r, i := p.x, p.i
mp[i] += 1
for len(mp) == len(nums) { // 每个列表都至少包含一个数
l, i := pairs[left].x, pairs[left].i
if r-l < ansR-ansL {
ansL, ansR = l, r
}
mp[i] -= 1
if mp[i] == 0 {
delete(mp, i)
}
left += 1
}
}
return []int{ansL, ansR}
}
func main() {
testCases := [][][]int{
[][]int{
[]int{4, 10, 15, 24, 26},
[]int{0, 9, 12, 20},
[]int{5, 18, 22, 30},
},
[][]int{
[]int{1, 2, 3},
[]int{1, 2, 3},
[]int{1, 2, 3},
},
}
for _, testCase := range testCases {
fmt.Println(smallestRange(testCase))
}
}