Posts published in August 2019

花花酱 LeetCode 1156. Swap For Longest Repeated Character Substring

By zxi on August 11, 2019

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

Example 1:

Input: text = "ababa"
Output: 3
Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.

Example 2:

Input: text = "aaabaaa"
Output: 6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.

Example 3:

Input: text = "aaabbaaa"
Output: 4

Example 4:

Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.

Example 5:

Input: text = "abcdef"
Output: 1

Constraints:

1 <= text.length <= 20000
text consist of lowercase English characters only.

Solution: HashTable

Pre-processing

Compute the longest repeated substring starts and ends with text[i].
Count the frequency of each letter.

Main

Loop through each letter
Check the left and right letter
- if they are the same, len = left + right
  - e.g1. “aa c aaa [b] aaaa” => len = 3 + 4 = 7
- if they are not the same, len = max(left, right)
  - e.g2. “aa [b] ccc d c” => len = max(2, 3) = 3
If the letter occurs more than len times, we can always find an extra one and swap it with the current letter => ++len
- e.g.1, count[“a”] = 9 > 7, len = 7 + 1 = 8
- e.g.2, count[“c”] = 4 > 3, len = 3 + 1 = 4

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

C++

// Author: Huahua

class Solution {

public:

int maxRepOpt1(string text) {

int n = text.length();

// Length of repeted substring ends with text[i]

vector<vector<int>> len1(n, vector<int>(26));

// Length of repeated substring starts with text[i]

vector<vector<int>> len2(n, vector<int>(26));

vector<int> counts(26);

int last = -1; // not a letter

int l = 0;

int ans = 0;

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

const int c = text[i] - 'a';

if (c == last) {

++l;

} else {

last = c;

l = 1;

}

len1[i][c] = l;

len2[i - l + 1][c] = l;

++counts[c];

ans = max(ans, l);

}

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

int cl = text[i - 1] - 'a';

int cr = text[i + 1] - 'a';

int left = len1[i - 1][cl];

int right = len2[i + 1][cr];

int count = 0;

if (cl != cr) {

// e.g. "c aaa b cccc" => "b aaa ccccc"

count = max(left + (counts[cl] > left ? 1 : 0),

right + (counts[cr] > right ? 1 : 0));

} else {

// e.g. "a c aaa b aaaa" => "b c aaaaaaaa"

count = left + right;

if (counts[cl] > count) ++count;

}

ans = max(ans, count);

}

return ans;

}

};

花花酱 LeetCode 1155. Number of Dice Rolls With Target Sum

By zxi on August 11, 2019

You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of f^d total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Example 1:

Input: d = 1, f = 6, target = 3
Output: 1
Explanation: 
You throw one die with 6 faces.  There is only one way to get a sum of 3.

Example 2:

Input: d = 2, f = 6, target = 7
Output: 6
Explanation: 
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4:

Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5:

Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation: 
The answer must be returned modulo 10^9 + 7.

Constraints:

1 <= d, f <= 30
1 <= target <= 1000

Solution: DP

definition: dp[i][k] := ways to have sum of k using all first i dices.
Init: dp[0][0] = 1
transition: dp[i][k] = sum(dp[i – 1][k – j]), 1 <= j <= f
ans: dp[d][target]

Time complexity: O(|d|*|f|*target)
Space complexity: O(|d|*target) -> O(target)

C++

// Author: Huahua, 32ms, 10.8MB

class Solution {

public:

int numRollsToTarget(int d, int f, int target) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> dp(d + 1, vector<int>(target + 1));

dp[0][0] = 1;

for (int i = 1; i <= d; ++i)

for (int j = 1; j <= f; ++j)

for (int k = j; k <= target; ++k)

dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % kMod;

return dp[d][target];

}

};

O(target)

// Author: Huahua, 40 ms, 8.8MB

class Solution {

public:

int numRollsToTarget(int d, int f, int target) {

constexpr int kMod = 1e9 + 7;

vector<int> dp(target + 1);

dp[0] = 1;

for (int i = 1; i <= d; ++i)

for (int k = target; k >= 0; --k) {

dp[k] = 0;

for (int j = 1; j <= f && j <= k; ++j)

dp[k] = (dp[k] + dp[k - j]) % kMod;

}

return dp[target];

}

};

Python

# Author: Huahua

from functools import lru_cache

class Solution:

def numRollsToTarget(self, d: int, f: int, target: int) -> int:

mod = 10 ** 9 + 7

# Number of ways to have target t using i dices.

@lru_cache(maxsize=None)

def dp(i, t):

if i == 0: return 1 if t == 0 else 0

# Pruning 388 ms -> 132 ms

if t > f * i or t < i: return 0

ans = 0

for k in range(1, f + 1):

ans = (ans + dp(i - 1, t - k)) % mod

return ans

return dp(d, target)

花花酱 LeetCode 1154. Day of the Year

By zxi on August 11, 2019

Given a string date representing a Gregorian calendar date formatted as YYYY-MM-DD, return the day number of the year.

Example 1:

Input: date = "2019-01-09"
Output: 9
Explanation: Given date is the 9th day of the year in 2019.

Example 2:

Input: date = "2019-02-10"
Output: 41

Example 3:

Input: date = "2003-03-01"
Output: 60

Example 4:

Input: date = "2004-03-01"
Output: 61

Constraints:

date.length == 10
date[4] == date[7] == '-', and all other date[i]‘s are digits
date represents a calendar date between Jan 1st, 1900 and Dec 31, 2019.

Solution:

Key: checking whether that year is a leap year or not.
is_leap = (year % 4 == 0 and year % 100 !=0) or year % 400 == 0

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

Python

# Author: Huahua

class Solution:

def dayOfYear(self, date: str) -> int:

y, m, d = int(date.split("-")[0]), int(date.split("-")[1]), int(date.split("-")[2])

leap = (y % 4 == 0 and y % 100 != 0) or y % 400 == 0

days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

s = sum(days[0:m-1]) + d

if leap and m > 2: s += 1

return s

花花酱 LeetCode 1157. Online Majority Element In Subarray

By zxi on August 10, 2019

Implementing the class MajorityChecker, which has the following API:

MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
int query(int left, int right, int threshold) has arguments such that:
- 0 <= left <= right < arr.length representing a subarray of arr;
- 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right]that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

1 <= arr.length <= 20000
1 <= arr[i] <= 20000
For each query, 0 <= left <= right < len(arr)
For each query, 2 * threshold > right - left + 1
The number of queries is at most 10000

Solution 0: Brute Force TLE

For each range, find the majority element in O(n) time / O(n) or O(1) space.

Solution 1: Cache the range result

Cache the result for each range: mode and frequency

Time complexity:
init: O(1)
query: O(|right – left|)
total queries: O(sum(right_i – left_i)), right_i, left_i are bounds of unique ranges.
Space complexity:
init: O(1)
query: O(20000)

C++

// Author: Huahua, 568ms, 39.6 MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {}

int query(int left, int right, int threshold) {

int key = left * 20000 + right;

if (!seen.count(key)) {

int c[20001] = {0};

int best = (right - left) / 2;

int best_num = -1;

for (int i = left; i <= right; ++i) {

if (++c[nums[i]] > best) {

best = c[nums[i]];

best_num = nums[i];

}

seen[key] = {best_num, best};

}

return seen[key].second >= threshold ? seen[key].first : -1;

}

private:

unordered_map<int, pair<int, int>> seen;

const vector<int>& nums;

};

Solution 2: HashTable + binary search

Preprocessing: use a hashtable to store the indices of each element. And sort by frequency of the element in descending order.
Query: iterator over (total_freq, num) pair, if freq >= threshold do a binary search to find the frequency of the given range for num in O(logn).

Time complexity:
Init: O(nlogn)
Query: worst case: O(nlogn), best case: O(logn)

C++

// Author: Huahua, 156 ms, 44.7MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {

const int max_n = *max_element(begin(nums), end(nums));

m = vector<vector<int>>(max_n + 1);

for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);

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

if (m[n].size()) f.emplace_back(m[n].size(), n);

}

sort(rbegin(f), rend(f));

}

int query(int left, int right, int threshold) {

for (const auto& p : f) {

if (p.first < threshold) return -1;

int n = p.second;

const auto& idx = m[n];

int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);

if (count >= threshold) return n;

}

return -1;

}

private:

const vector<int>& nums;

vector<vector<int>> m; // num -> {indices}

vector<pair<int, int>> f; // {freq, num}

};

Solution 2+: Randomization

Randomly pick a num in range [left, right] and check its freq, try k (e.g. 30) times. If a majority element exists, you should find it with error rate 1/2^k.

Time complexity:
Init: O(n)
Query: O(30 * logn)
Space complexity: O(n)

C++

// Author: Huahua, 240ms, 45.6MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {

for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);

}

int query(int left, int right, int threshold) {

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

int n = nums[rand() % (right - left + 1) + left];

const auto& idx = m[n];

int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);

if (count >= threshold) return n;

}

return -1;

}

private:

unordered_map<int, vector<int>> m; // num -> {indices}

const vector<int>& nums;

};

花花酱 LeetCode 1110. Delete Nodes And Return Forest

By zxi on August 8, 2019

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

Solution: Recursion / Post-order traversal

Recursively delete nodes on left subtree and right subtree and return the trimmed tree.
if the current node needs to be deleted, then its non-null children will be added to output array.

Time complexity: O(n)
Space complexity: O(|d| + h)

C++

// Author: Huahua

class Solution {

public:

vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {

vector<TreeNode*> ans;

unordered_set<int> s{begin(to_delete), end(to_delete)};

function<TreeNode*(TreeNode*)> del = [&](TreeNode* n) -> TreeNode* {

if (!n) return nullptr;

if (n->left) n->left = del(n->left);

if (n->right) n->right = del(n->right);

if (!s.count(n->val)) return n;

if (n->left) ans.push_back(n->left);

if (n->right) ans.push_back(n->right);

return nullptr;

};

TreeNode* r = del(root);

if (r) ans.push_back(r);

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:

ans = []

ds = set(to_delete)

def process(n):

if not n: return None

n.left, n.right = process(n.left), process(n.right)

if n.val not in ds: return n

if n.left: ans.append(n.left)

if n.right: ans.append(n.right)

return None

root = process(root)

if root: ans.append(root)

return ans