Posts tagged as “dp”

花花酱 LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

By zxi on August 11, 2020

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

Solution: Prefix Sum + DP

Use a hashmap index to record the last index when a given prefix sum occurs.
dp[i] := max # of non-overlapping subarrays of nums[0~i], nums[i] is not required to be included.
dp[i+1] = max(dp[i], // skip nums[i]
dp[index[sum – target] + 1] + 1) // use nums[i] to form a new subarray
ans = dp[n]

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

C++

class Solution {

public:

int maxNonOverlapping(vector<int>& nums, int target) {

const int n = nums.size();

vector<int> dp(n + 1, 0); // ans at nums[i];

unordered_map<int, int> index; // {prefix sum -> last_index}

index[0] = -1;

int sum = 0;

for (int i = 0; i < n; ++i) {

sum += nums[i];

int t = sum - target;

dp[i + 1] = dp[i];

if (index.count(t))

dp[i + 1] = max(dp[i + 1], dp[index[t] + 1] + 1);

index[sum] = i;

}

return dp[n];

}

};

花花酱 LeetCode 1537. Get the Maximum Score

By zxi on August 2, 2020

You are given two sorted arrays of distinct integers nums1 and nums2.

A validpath is defined as follows:

Choose array nums1 or nums2 to traverse (from index-0).
Traverse the current array from left to right.
If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].

Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].

Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].

Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61

Constraints:

1 <= nums1.length <= 10^5
1 <= nums2.length <= 10^5
1 <= nums1[i], nums2[i] <= 10^7
nums1 and nums2 are strictly increasing.

Solution: Two Pointers + DP

Since numbers are strictly increasing, we can always traverse the smaller one using two pointers.
Traversing ([2,4,5,8,10], [4,6,8,10])
will be like [2, 4/4, 5, 6, 8, 10/10]
It two nodes have the same value, we have two choices and pick the larger one, then both move nodes one step forward. Otherwise, the smaller node moves one step forward.
dp1[i] := max path sum ends with nums1[i-1]
dp2[j] := max path sum ends with nums2[j-1]
if nums[i -1] == nums[j – 1]:
dp1[i] = dp2[j] = max(dp[i-1], dp[j-1]) + nums[i -1]
i += 1, j += 1
else if nums[i – 1] < nums[j – 1]:
dp[i] = dp[i-1] + nums[i -1]
i += 1
else if nums[j – 1] < nums[i – 1]:
dp[j] = dp[j-1] + nums[j -1]
j += 1
return max(dp1[-1], dp2[-1])

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

C++

class Solution {

public:

int maxSum(vector<int>& nums1, vector<int>& nums2) {

constexpr int kMod = 1e9 + 7;

const int n1 = nums1.size();

const int n2 = nums2.size();

vector<long> dp1(n1 + 1); // max path sum ends with nums1[i-1]

vector<long> dp2(n2 + 1); // max path sum ends with nums2[j-1]

int i = 0;

int j = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

// Same, two choices, pick the larger one.

dp2[j + 1] = dp1[i + 1] = max(dp1[i], dp2[j]) + nums1[i];

++i; ++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

dp1[i + 1] = dp1[i] + nums1[i];

++i;

} else if (j < n2 && (i == n1 || nums2[j] < nums1[i])) {

dp2[j + 1] = dp2[j] + nums2[j];

++j;

}

return max(dp1.back(), dp2.back()) % kMod;

}

};

Java

class Solution {

public int maxSum(int[] nums1, int[] nums2) {

final int kMod = 1_000_000_007;

int n1 = nums1.length;

int n2 = nums2.length;

int i = 0;

int j = 0;

long a = 0;

long b = 0;

while (i < n1 || j < n2) {

if (i < n1 && j < n2 && nums1[i] == nums2[j]) {

a = b = Math.max(a, b) + nums1[i];

++i;

++j;

} else if (i < n1 && (j == n2 || nums1[i] < nums2[j])) {

a += nums1[i++];

} else {

b += nums2[j++];

}

return (int)(Math.max(a, b) % kMod);

}

python3

class Solution:

def maxSum(self, nums1: List[int], nums2: List[int]) -> int:

n1, n2 = len(nums1), len(nums2)

i, j = 0, 0

a, b = 0, 0

while i < n1 or j < n2:

if i < n1 and j < n2 and nums1[i] == nums2[j]:

a = b = max(a, b) + nums1[i]

i += 1

j += 1

elif i < n1 and (j == n2 or nums1[i] < nums2[j]):

a += nums1[i]

i += 1

else:

b += nums2[j]

j += 1

return max(a, b) % (10**9 + 7)

花花酱 LeetCode 1513. Number of Substrings With Only 1s

By zxi on July 29, 2020

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.

Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.

Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.

Example 4:

Input: s = "000"
Output: 0

Constraints:

s[i] == '0' or s[i] == '1'
1 <= s.length <= 10^5

Solution: DP / Prefix Sum

dp[i] := # of all 1 subarrays end with s[i].
dp[i] = dp[i-1] if s[i] == ‘1‘ else 0
ans = sum(dp)
s=1101
dp[0] = 1 // 1
dp[1] = 2 // 11, *1
dp[2] = 0 // None
dp[3] = 1 // ***1
ans = 1 + 2 + 1 = 5

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

C++

class Solution {

public:

int numSub(string s) {

constexpr int kMod = 1e9 + 7;

long ans = 0;

vector<int> dp(s.length() + 1);

for (int i = 1; i <= s.length(); ++i) {

dp[i] = s[i - 1] == '1' ? dp[i - 1] + 1 : 0;

ans += dp[i];

}

return ans % kMod;

}

};

dp[i] only depends on dp[i-1], we can reduce the space complexity to O(1)

C++

class Solution {

public:

int numSub(string s) {

constexpr int kMod = 1e9 + 7;

long ans = 0;

int cur = 0;

for (char c : s) {

cur = c == '1' ? cur + 1 : 0;

ans += cur;

}

return ans % kMod;

}

};

Java

class Solution {

public int numSub(String s) {

final int kMod = 1_000_000_000 + 7;

int ans = 0;

int cur = 0;

for (int i = 0; i < s.length(); ++i) {

cur = s.charAt(i) == '1' ? cur + 1 : 0;

ans = (ans + cur) % kMod;

}

return ans;

}

Python3

class Solution:

def numSub(self, s: str) -> int:

kMod = 10**9 + 7

ans = 0

cur = 0

for c in s:

cur = cur + 1 if c == '1' else 0

ans += cur

return ans % kMod

花花酱 LeetCode 1531. String Compression II

By zxi on July 26, 2020

Run-length encoding is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "aabccc" we replace "aa" by "a2" and replace "ccc" by "c3". Thus the compressed string becomes "a2bc3".

Notice that in this problem, we are not adding '1' after single characters.

Given a string s and an integer k. You need to delete at most k characters from s such that the run-length encoded version of s has minimum length.

Find the minimum length of the run-length encoded version of s after deleting at most k characters.

Example 1:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

Example 2:

Input: s = "aabbaa", k = 2
Output: 2
Explanation: If we delete both 'b' characters, the resulting compressed string would be "a4" of length 2.

Example 3:

Input: s = "aaaaaaaaaaa", k = 0
Output: 3
Explanation: Since k is zero, we cannot delete anything. The compressed string is "a11" of length 3.

Constraints:

1 <= s.length <= 100
0 <= k <= s.length
s contains only lowercase English letters.

Solution 0: Brute Force DFS (TLE)

Time complexity: O(C(n,k))
Space complexity: O(k)

C++

class Solution {

public:

int getLengthOfOptimalCompression(string s, int k) {

const int n = s.length();

auto encode = [&]() -> int {

char p = '$';

int count = 0;

int len = 0;

for (char c : s) {

if (c == '.') continue;

if (c != p) {

p = c;

count = 0;

}

++count;

if (count <= 2 || count == 10 || count == 100)

++len;

}

return len;

};

function<int(int, int)> dfs = [&](int start, int k) -> int {

if (start == n || k == 0) return encode();

int ans = n;

for (int i = start; i < n; ++i) {

char c = s[i];

s[i] = '.'; // delete

ans = min(ans, dfs(i + 1, k - 1));

s[i] = c;

}

return ans;

};

return dfs(0, k);

}

};

Solution1: DP

State:
i: the start index of the substring
last: last char
len: run-length
k: # of chars that can be deleted.

base case:
1. k < 0: return inf # invalid
2. i >= s.length(): return 0 # done

Transition:
1. if s[i] == last: return carry + dp(i + 1, last, len + 1, k)

2. if s[i] != last:
return min(1 + dp(i + 1, s[i], 1, k, # start a new group with s[i]
dp(i + 1, last, len, k -1) # delete / skip s[i], keep it as is.

Time complexity: O(n^3*26)
Space complexity: O(n^3*26)

C++

int cache[101][27][101][101];

class Solution {

public:

int getLengthOfOptimalCompression(string s, int k) {

memset(cache, -1, sizeof(cache));

// Min length of compressioned string of s[i:]

// 1. last char is |last|

// 2. current run-length is len

// 3. we can delete k chars.

function<int(int, int, int, int)> dp =

[&](int i, int last, int len, int k) {

if (k < 0) return INT_MAX / 2;

if (i >= s.length()) return 0;

int& ans = cache[i][last][len][k];

if (ans != -1) return ans;

if (s[i] - 'a' == last) {

// same as the previous char, no need to delete.

int carry = (len == 1 || len == 9 || len == 99);

ans = carry + dp(i + 1, last, len + 1, k);

} else {

ans = min(1 + dp(i + 1, s[i] - 'a', 1, k), // keep s[i]

dp(i + 1, last, len, k - 1)); // delete s[i]

}

return ans;

};

return dp(0, 26, 0, k);

}

};

State compression

dp[i][k] := min len of s[i:] encoded by deleting at most k charchters.

dp[i][k] = min(dp[i+1][k-1] # delete s[i]
encode_len(s[i~j] == s[i]) + dp(j+1, k – sum(s[i~j])) for j in range(i, n)) # keep

Time complexity: O(n^2*k)
Space complexity: O(n*k)

C++

// Author: Huahua

class Solution {

public:

int getLengthOfOptimalCompression(string s, int k) {

const int n = s.length();

vector<vector<int>> cache(n, vector<int>(k + 1, -1));

function<int(int, int)> dp = [&](int i, int k) -> int {

if (k < 0) return n;

if (i + k >= n) return 0;

int& ans = cache[i][k];

if (ans != -1) return ans;

ans = dp(i + 1, k - 1); // delete

int len = 0;

int same = 0;

int diff = 0;

for (int j = i; j < n && diff <= k; ++j) {

if (s[j] == s[i] && ++same) {

if (same <= 2 || same == 10 || same == 100) ++len;

} else {

++diff;

}

ans = min(ans, len + dp(j + 1, k - diff));

}

return ans;

};

return dp(0, k);

}

};

Java

// Author: Huahua

class Solution {

private int[][] dp;

private char[] s;

private int n;

public int getLengthOfOptimalCompression(

String s, int k) {

this.s = s.toCharArray();

this.n = s.length();

this.dp = new int[n][k + 1];

for (int[] row : dp)

Arrays.fill(row, -1);

return dp(0, k);

}

private int dp(int i, int k) {

if (k < 0) return this.n;

if (i + k >= n) return 0; // done or delete all.

int ans = dp[i][k];

if (ans != -1) return ans;

ans = dp(i + 1, k - 1); // delete s[i]

int len = 0;

int same = 0;

int diff = 0;

for (int j = i; j < n && diff <= k; ++j) {

if (s[j] == s[i]) {

++same;

if (same <= 2 || same == 10 || same == 100) ++len;

} else {

++diff;

}

ans = Math.min(ans, len + dp(j + 1, k - diff));

}

dp[i][k] = ans;

return ans;

}

Python3

# Author: Huahua

class Solution:

def getLengthOfOptimalCompression(self, s: str, k: int) -> int:

n = len(s)

@functools.lru_cache(maxsize=None)

def dp(i, k):

if k < 0: return n

if i + k >= n: return 0

ans = dp(i + 1, k - 1)

l = 0

same = 0

for j in range(i, n):

if s[j] == s[i]:

same += 1

if same <= 2 or same == 10 or same == 100:

l += 1

diff = j - i + 1 - same

if diff < 0: break

ans = min(ans, l + dp(j + 1, k - diff))

return ans

return dp(0, k)

花花酱 LeetCode 1524. Number of Sub-arrays With Odd Sum

By zxi on July 25, 2020

Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

Example 4:

Input: arr = [100,100,99,99]
Output: 4

Example 5:

Input: arr = [7]
Output: 1

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 100

Solution: DP

We would like to know how many subarrays end with arr[i] have odd or even sums.

dp[i][0] := # end with arr[i] has even sum
dp[i][1] := # end with arr[i] has even sum

if arr[i] is even:

dp[i][0]=dp[i-1][0] + 1, dp[i][1]=dp[i-1][1]

else:

dp[i][1]=dp[i-1][0], dp[i][0]=dp[i-1][0] + 1

ans = sum(dp[i][1])

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

C++

class Solution {

public:

int numOfSubarrays(vector<int>& arr) {

const int n = arr.size();

constexpr int kMod = 1e9 + 7;

// dp[i][0] # of subarrays ends with a[i-1] have even sums.

// dp[i][1] # of subarrays ends with a[i-1] have odd sums.

vector<vector<int>> dp(n + 1, vector<int>(2));

long ans = 0;

for (int i = 1; i <= n; ++i) {

if (arr[i - 1] & 1) {

dp[i][0] = dp[i - 1][1];

dp[i][1] = dp[i - 1][0] + 1;

} else {

dp[i][0] = dp[i - 1][0] + 1;

dp[i][1] = dp[i - 1][1];

}

ans += dp[i][1];

}

return ans % kMod;

}

};

Java

// Author: Huahua

class Solution {

public int numOfSubarrays(int[] arr) {

long ans = 0, odd = 0, even = 0;

for (int x : arr) {

even += 1;

if (x % 2 == 1) {

long t = even; even = odd; odd = t;

}

ans += odd;

}

return (int)(ans % (int)(1e9 + 7));

}

Python3

# Author: Huahua

class Solution:

def numOfSubarrays(self, arr: List[int]) -> int:

ans, odd, even = 0, 0, 0

for x in arr:

if x & 1:

odd, even = even + 1, odd

else:

odd, even = odd, even + 1

ans += odd

return ans % int(1e9 + 7)