Huahua's Tech Road

花花酱 LeetCode 1163. Last Substring in Lexicographical Order

By zxi on August 18, 2019

Given a string s, return the last substring of s in lexicographical order.

Example 1:

Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: "leetcode"
Output: "tcode"

Note:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Key observation: The last substring must be a suffix of the original string, can’t a substring in the middle since we can always extend it.
e.g. leetcode -> tcode, can’t be “t”, “tc”, “tco”, “tcod”

Solution 1: Brute Force

Try all possible suffixes.
Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua, 452 ms, 12.8 MB

class Solution {

public:

string lastSubstring(string_view s) {

string_view ans;

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

if (s.substr(i) > ans) ans = s.substr(i);

return string(ans);

}

};

Solution 2: Keep max and compare with candidates

Find the first largest letter as a starting point, whenever there is a same letter, keep it as a candidate and compare with the current best. If the later is larger, take over the current best.

e.g. “acbacbc”

“c” > “a”, the first “c” becomes the best.
“c” = “c”, the second “c” becomes a candidate
starting compare best and candidate.
“cb” = “cb”
“cba” < “cbc”, cand_i is the new best.

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

C++

// Author: Huahua

class Solution {

public:

string lastSubstring(string s) {

int max_i = 0;

char max_c = 0;

int cand_i = 0;

int l = 0;

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

if (s[i] > max_c) {

// Find a better starting point.

max_c = s[i];

max_i = i;

cand_i = -1;

l = 1;

} else if (cand_i != -1) {

// Has a candidate.

if (s[i] > s[max_i + l]) {

// The candidate is larger.

max_i = cand_i;

cand_i = -1;

} else if (s[i] == s[max_i + l]) {

// The candidate is the same as current best.

++l;

} else {

// The candidate is smaller, no longer needed.

cand_i = -1;

}

} else if (s[i] == max_c) {

// Find a new candidate, starting with length 1.

cand_i = i;

l = 1;

}

return s.substr(max_i);

}

};

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

}

};