Huahua’s Tech Road

花花酱 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 1529. Bulb Switcher IV

By zxi on July 26, 2020

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

Choose any bulb (index i) of your current configuration.
Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

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

Solution: XOR

Flip from left to right, since flipping the a bulb won’t affect anything in the left.
We count how many times flipped so far, and that % 2 will be the state for all the bulb to the right.
If the current bulb’s state != target, we have to flip once.

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

C++

class Solution {

public:

int minFlips(string target) {

int ans = 0;

int cur = 0;

for (char c : target) {

if (c - '0' != cur) {

cur ^= 1;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1530. Number of Good Leaf Nodes Pairs

By zxi on July 25, 2020

Given the root of a binary tree and an integer distance. A pair of two different leaf nodes of a binary tree is said to be good if the length of the shortest path between them is less than or equal to distance.

Return the number of good leaf node pairs in the tree.

Example 1:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

Example 2:

Input: root = [1,2,3,4,5,6,7], distance = 3
Output: 2
Explanation: The good pairs are [4,5] and [6,7] with shortest path = 2. The pair [4,6] is not good because the length of ther shortest path between them is 4.

Example 3:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2], distance = 3
Output: 1
Explanation: The only good pair is [2,5].

Example 4:

Input: root = [100], distance = 1
Output: 0

Example 5:

Input: root = [1,1,1], distance = 2
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 2^10].
Each node’s value is between [1, 100].
1 <= distance <= 10

Solution: Brute Force

Since n <= 1024, and distance <= 10, we can collect all leaf nodes and try all pairs.

Time complexity: O(|leaves|^2)
Space complexity: O(n)

C++

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

unordered_map<TreeNode*, TreeNode*> parents;

vector<TreeNode*> leaves;

function<void(TreeNode*, TreeNode*)> dfs = [&](TreeNode* c, TreeNode* p) {

if (!c) return;

parents[c] = p;

dfs(c->left, c);

dfs(c->right, c);

if (!c->left && !c->right) leaves.push_back(c);

};

dfs(root, nullptr);

unordered_map<TreeNode*, int> a;

auto isGood = [&](TreeNode* n) -> int {

for (int i = 0; i < distance && n; ++i, n = parents[n])

if (a.count(n) && a[n] + i <= distance) return 1;

return 0;

};

int ans = 0;

for (int i = 0; i < leaves.size(); ++i) {

TreeNode* n1 = leaves[i];

a.clear();

for (int k = 0; k < distance && n1; ++k, n1 = parents[n1])

a[n1] = k;

for (int j = i + 1; j < leaves.size(); ++j)

ans += isGood(leaves[j]);

}

return ans;

}

};

Solution 2: Post order traversal

For each node, compute the # of good leaf pair under itself.
1. count the frequency of leaf node at distance 1, 2, …, d for both left and right child.
2. ans += l[i] * r[j] (i + j <= distance) cartesian product
3. increase the distance by 1 for each leaf node when pop
Time complexity: O(n*D^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countPairs(TreeNode* root, int distance) {

int ans = 0;

function<vector<int>(TreeNode*)> dfs

= [&](TreeNode* c) -> vector<int> {

// f[i] = number of leaves node at distance i.

vector<int> f(distance + 1);

if (!c) return f;

if (!c->left && !c->right) {

f[0] = 1; // a single leaf node

return f;

}

const vector<int>& l = dfs(c->left);

const vector<int>& r = dfs(c->right);

for (int i = 0; i + 1 <= distance; ++i)

for (int j = 0; i + j + 2 <= distance; ++j)

ans += l[i] * r[j];

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

f[i + 1] = l[i] + r[i];

return f;

};

dfs(root);

return ans;

}

};

Java

class Solution {

private int D;

private int ans;

public int countPairs(TreeNode root, int distance) {

this.D = distance;

this.ans = 0;

dfs(root);

return ans;

}

private int[] dfs(TreeNode root) {

int[] f = new int[D + 1];

if (root == null) return f;

if (root.left == null && root.right == null) {

f[0] = 1;

return f;

}

int[] fl = dfs(root.left);

int[] fr = dfs(root.right);

for (int i = 0; i + 1 <= D; ++i)

for (int j = 0; i + j + 2 <= D; ++j)

this.ans += fl[i] * fr[j];

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

f[i + 1] = fl[i] + fr[i];

return f;

}

Python3

# Author: Huahua

class Solution:

def countPairs(self, root: TreeNode, D: int) -> int:

def dfs(node):

f = [0] * (D + 1)

if not node: return f, 0

if not node.left and not node.right:

f[0] = 1

return f, 0

fl, pl = dfs(node.left)

fr, pr = dfs(node.right)

pairs = 0

for dl, cl in enumerate(fl):

for dr, cr in enumerate(fr):

if dl + dr + 2 <= D: pairs += cl * cr

for i in range(D):

f[i + 1] = fl[i] + fr[i]

return f, pl + pr + pairs

return dfs(root)[1]

花花酱 1528. Shuffle String

By zxi on July 25, 2020

Given a string s and an integer array indices of the same length.

The string s will be shuffled such that the character at the i^th position moves to indices[i] in the shuffled string.

Return the shuffled string.

Example 1:

Input: s = "codeleet", indices = [4,5,6,7,0,2,1,3]
Output: "leetcode"
Explanation: As shown, "codeleet" becomes "leetcode" after shuffling.

Example 2:

Input: s = "abc", indices = [0,1,2]
Output: "abc"
Explanation: After shuffling, each character remains in its position.

Example 3:

Input: s = "aiohn", indices = [3,1,4,2,0]
Output: "nihao"

Example 4:

Input: s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
Output: "arigatou"

Example 5:

Input: s = "art", indices = [1,0,2]
Output: "rat"

Constraints:

s.length == indices.length == n
1 <= n <= 100
s contains only lower-case English letters.
0 <= indices[i] < n
All values of indices are unique (i.e. indices is a permutation of the integers from 0 to n - 1).

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

string restoreString(string s, vector<int>& indices) {

string ans(s);

for (int i = 0; i < indices.size(); ++i)

ans[indices[i]] = s[i];

return ans;

}

};

Java

// Author: Huahua

class Solution {

public String restoreString(String s, int[] indices) {

char[] ans = new char[s.length()];

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

ans[indices[i]] = s.charAt(i);

return new String(ans);

}

Pyhton3

class Solution:

def restoreString(self, s: str, indices: List[int]) -> str:

ans = [None] * len(s)

for i, idx in enumerate(indices):

ans[idx] = s[i]

return ''.join(ans)

Huahua's Tech Road

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

Solution: DP / Prefix Sum

C++

C++

Java

Python3

花花酱 LeetCode 1531. String Compression II

Solution 0: Brute Force DFS (TLE)

C++

Solution1: DP

C++

State compression

C++

Java

Python3

花花酱 LeetCode 1529. Bulb Switcher IV

Solution: XOR

C++

花花酱 LeetCode 1530. Number of Good Leaf Nodes Pairs

Solution: Brute Force

C++

Solution 2: Post order traversal

C++

Java

Python3

花花酱 1528. Shuffle String

Solution: Simulation

C++

Java

Pyhton3