Posts published in “Dynamic Programming”

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

花花酱 LeetCode 1504. Count Submatrices With All Ones

By zxi on July 5, 2020

Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.

Example 1:

Input: mat = [[1,0,1],
              [1,1,0],
              [1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2:

Input: mat = [[0,1,1,0],
              [0,1,1,1],
              [1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Example 3:

Input: mat = [[1,1,1,1,1,1]]
Output: 21

Example 4:

Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5

Constraints:

1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1

Solution 1: Brute Force w/ Pruning

Time complexity: O(m^2*n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numSubmat(vector<vector<int>>& mat) {

const int R = mat.size();

const int C = mat[0].size();

// # of sub matrices with top-left at (sr, sc)

auto subMats = [&](int sr, int sc) {

int max_c = C;

int count = 0;

for (int r = sr; r < R; ++r)

for (int c = sc; c < max_c; ++c)

if (mat[r][c]) {

++count;

} else {

max_c = c;

}

return count;

};

int ans = 0;

for (int r = 0; r < R; ++r)

for (int c = 0; c < C; ++c)

ans += subMats(r, c);

return ans;

}

};

花花酱 LeetCode 1494. Parallel Courses II

By zxi on June 27, 2020

Given the integer n representing the number of courses at some university labeled from 1 to n, and the array dependencies where dependencies[i] = [x_i, y_i] represents a prerequisite relationship, that is, the course x_i must be taken before the course y_i. Also, you are given the integer k.

In one semester you can take at most k courses as long as you have taken all the prerequisites for the courses you are taking.

Return the minimum number of semesters to take all courses. It is guaranteed that you can take all courses in some way.

Example 1:

Input: n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
Output: 3 
Explanation: The figure above represents the given graph. In this case we can take courses 2 and 3 in the first semester, then take course 1 in the second semester and finally take course 4 in the third semester.

Example 2:

Input: n = 5, dependencies = [[2,1],[3,1],[4,1],[1,5]], k = 2
Output: 4 
Explanation: The figure above represents the given graph. In this case one optimal way to take all courses is: take courses 2 and 3 in the first semester and take course 4 in the second semester, then take course 1 in the third semester and finally take course 5 in the fourth semester.

Example 3:

Input: n = 11, dependencies = [], k = 2
Output: 6

Constraints:

1 <= n <= 15
1 <= k <= n
0 <= dependencies.length <= n * (n-1) / 2
dependencies[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
All prerequisite relationships are distinct, that is, dependencies[i] != dependencies[j].
The given graph is a directed acyclic graph.

Solution: DP / Bitmask

NOTE: This is a NP problem, any polynomial-time algorithm is incorrect otherwise P = NP.

Variant 1:
dp[m] := whether state m is reachable, where m is the bitmask of courses studied.
For each semester, we enumerate all possible states from 0 to 2^n – 1, if that state is reachable, then we choose c (c <= k) courses from n and check whether we can study those courses.
If we can study those courses, we have a new reachable state, we set dp[m | courses] = true.

Time complexity: O(n*2^n*2^n) = O(n*n^4) <– This will be much smaller in practice.
and can be reduced to O(n*3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 52 ms, 14.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp(i)[s] := reachable(s) at semester i.

vector<int> dp(S);

dp[0] = 1;

for (int d = 1; d <= n; ++d) { // at most n semesters.

vector<int> tmp(S); // start a new semesters.

for (int s = 0; s < S; ++s) {

if (!dp[s]) continue; // not a reachable state.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

tmp[s | mask] = 1;

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k) {

tmp[s | c] = 1;

}

if (tmp.back()) return d;

}

dp.swap(tmp);

}

return -1;

}

};

Variant 2:
dp[m] := min semesters to reach state m.
dp[m | c] = min{dp[m | c], dp[m] + 1}, if we can reach m | c from m.
This allows us to get rid of enumerate n semesters.
Time complexity: O(2^n*2^n) <– This will be much smaller in practice.
and can be reduced to O(3^n).
Space complexity: O(2^n)

C++

// Author: Huahua, 16 ms, 8.5 MB

class Solution {

public:

int minNumberOfSemesters(int n, vector<vector<int>>& dependencies, int k) {

const int kInf = 1e9;

const int S = 1 << n;

vector<int> deps(n); // deps[i] = dependency mask for course i.

for (const auto& d : dependencies)

deps[d[1] - 1] |= 1 << (d[0] - 1);

// dp[m] := min semesters to reach state m.

vector<int> dp(S, kInf);

dp[0] = 0;

for (int s = 0; s < S; ++s) {

if (dp[s] == kInf) continue; // not reachable.

// Generate a mask of courses we can study under state s.

int mask = 0;

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

if (!(s & (1 << i)) && (s & deps[i]) == deps[i])

mask |= (1 << i);

// Prunning, take all.

if (__builtin_popcount(mask) <= k) {

dp[s | mask] = min(dp[s | mask], dp[s] + 1);

} else {

// Try all subsets.

for (int c = mask; c; c = (c - 1) & mask)

if (__builtin_popcount(c) <= k)

dp[s | c] = min(dp[s | c], dp[s] + 1);

}

// Early termination?

if (dp.back() != kInf) return dp.back();

}

return dp.back();

}

};