Huahua’s Tech Road

花花酱 LeetCode 1160. Find Words That Can Be Formed by Characters

By zxi on August 17, 2019

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

Solution: Hashtable

Use a hashtable to store each letter’s frequency of the string and compare that with each word.

Time complexity: O(n + sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua, 72 ms, 20 MB

class Solution {

public:

int countCharacters(vector<string>& words, string chars) {

vector<int> counts(26);

for (char c : chars) ++counts[c - 'a'];

int ans = 0;

for (const string& word : words) {

vector<int> cur(26);

bool valid = true;

for (char c: word)

if (++cur[c - 'a'] > counts[c - 'a']) {

valid = false;

break;

}

if (valid) ans += word.length();

}

return ans;

}

};

Python#

# Author: Huahua

class Solution:

def countCharacters(self, words: List[str], chars: str) -> int:

counts = collections.Counter(chars)

def isValid(word):

cur = collections.Counter(word)

for c in cur:

if c not in counts or cur[c] > counts[c]:

return False

return True

ans = 0

for word in words:

ans += len(word) if isValid(word) else 0

return ans

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

By zxi on August 17, 2019

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Example 1:

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Note:

The number of nodes in the given tree is between 1 and 10^4.
-10^5 <= node.val <= 10^5

Solution: HashTable

Use a hash table / array to store the level sum.

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

C++

// Author: Huahua, 232 ms, 70.2 ms

class Solution {

public:

int maxLevelSum(TreeNode* root) {

vector<int> sums;

function<void(TreeNode*, int)> preorder = [&](TreeNode* n, int d) {

if (!n) return;

while (sums.size() <= d) sums.push_back(0);

sums[d] += n->val;

preorder(n->left, d + 1);

preorder(n->right, d + 1);

};

preorder(root, 1);

int max_sum = sums[1];

int ans = 1;

for (int i = 2; i < sums.size(); ++i)

if (sums[i] > max_sum) {

max_sum = sums[i];

ans = i;

}

return ans;

}

};

花花酱 LeetCode 1162. As Far from Land as Possible

By zxi on August 17, 2019

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1)is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

Solution: BFS

Put all land cells into a queue as source nodes and BFS for water cells, the last expanded one will be the farthest.

Time compleixty: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua, 48 ms, 13.4 MB

class Solution {

public:

int maxDistance(vector<vector<int>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

int ans = -1;

queue<int> q; // y*100 + x

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

for (int j = 0; j < m; ++j)

if (grid[i][j] == 1) q.push(i * 100 + j);

vector<int> dirs{0, -1, 0, 1, 0};

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int x = p % 100;

int y = p / 100;

if (grid[y][x] == 2)

ans = max(ans, steps);

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

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || tx >= m || ty < 0 || ty >= n || grid[ty][tx] != 0) continue;

grid[ty][tx] = 2;

q.push(ty * 100 + tx);

}

++steps;

}

return ans;

}

};

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

Huahua's Tech Road

花花酱 LeetCode 1160. Find Words That Can Be Formed by Characters

Solution: Hashtable

C++

Python#

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

Solution: HashTable

C++

花花酱 LeetCode 1162. As Far from Land as Possible

Solution: BFS

C++

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

Solution: HashTable

C++

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

Solution: DP

C++

O(target)

Python