Huahua’s Tech Road

LeetCode 1433. Check If a String Can Break Another String

By zxi on May 3, 2020

Given two strings: s1 and s2 with the same size, check if some permutation of string s1 can break some permutation of string s2 or vice-versa (in other words s2 can break s1).

A string x can break string y (both of size n) if x[i] >= y[i] (in alphabetical order) for all i between 0 and n-1.

Example 1:

Input: s1 = "abc", s2 = "xya"
Output: true
Explanation: "ayx" is a permutation of s2="xya" which can break to string "abc" which is a permutation of s1="abc".

Example 2:

Input: s1 = "abe", s2 = "acd"
Output: false 
Explanation: All permutations for s1="abe" are: "abe", "aeb", "bae", "bea", "eab" and "eba" and all permutation for s2="acd" are: "acd", "adc", "cad", "cda", "dac" and "dca". However, there is not any permutation from s1 which can break some permutation from s2 and vice-versa.

Example 3:

Input: s1 = "leetcodee", s2 = "interview"
Output: true

Constraints:

s1.length == n
s2.length == n
1 <= n <= 10^5
All strings consist of lowercase English letters.

Solution 1: Sort and compare

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

C++

// Author: Huahua

class Solution {

public:

bool checkIfCanBreak(string s1, string s2) {

sort(begin(s1), end(s1));

sort(begin(s2), end(s2));

int f1 = 1;

int f2 = 1;

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

f1 &= s1[i] <= s2[i];

f2 &= s1[i] >= s2[i];

}

return f1 || f2;

}

};

Solution 2: Counting Sort

The cumulative number of elements must be monotonic e.g. t1 >= t2 or t2 >= t1 for all the letters.

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

C++

// Author: Huahua

class Solution {

public:

bool checkIfCanBreak(string s1, string s2) {

vector<int> c1(26);

vector<int> c2(26);

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

++c1[s1[i] - 'a'];

++c2[s2[i] - 'a'];

}

int t1 = 0;

int t2 = 0;

int f1 = 1;

int f2 = 1;

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

t1 += c1[i];

t2 += c2[i];

f1 &= t1 <= t2;

f2 &= t2 <= t1;

}

return f1 || f2;

}

};

花花酱 LeetCode 1432. Max Difference You Can Get From Changing an Integer

By zxi on May 3, 2020

You are given an integer num. You will apply the following steps exactly two times:

Pick a digit x (0 <= x <= 9).
Pick another digit y (0 <= y <= 9). The digit y can be equal to x.
Replace all the occurrences of x in the decimal representation of num by y.
The new integer cannot have any leading zeros, also the new integer cannot be 0.

Let a and b be the results of applying the operations to num the first and second times, respectively.

Return the max difference between a and b.

Example 1:

Input: num = 555
Output: 888
Explanation: The first time pick x = 5 and y = 9 and store the new integer in a.
The second time pick x = 5 and y = 1 and store the new integer in b.
We have now a = 999 and b = 111 and max difference = 888

Example 2:

Input: num = 9
Output: 8
Explanation: The first time pick x = 9 and y = 9 and store the new integer in a.
The second time pick x = 9 and y = 1 and store the new integer in b.
We have now a = 9 and b = 1 and max difference = 8

Example 3:

Input: num = 123456
Output: 820000

Example 4:

Input: num = 10000
Output: 80000

Example 5:

Input: num = 9288
Output: 8700

Constraints:

1 <= num <= 10^8

Solution 1: Brute Force

Try all possible pairs of (x, y)

Time complexity: O(10*10*logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int maxDiff(int num) {

int min_num = INT_MAX;

int max_num = INT_MIN;

for (char x = '0'; x <= '9'; ++x)

for (char y = '0'; y <= '9'; ++y) {

string n = to_string(num);

for (char& c : n)

if (c == x) c = y;

if (n[0] == '0') continue;

int v = stoi(n);

min_num = min(min_num, v);

max_num = max(max_num, v);

}

return max_num - min_num;

}

};

Solution 2: Greedy

Maximize A and Minimize B

A – B will the answer.

To maximize A, find the left most digit that is not 9, replace that digit with 9.
e.g. 121 => 919
e.g. 9981 => 9991
To minimize B, fin the left most digit that is not 1 or 0, replace that digit with 0 (if not the first one) or 1.
e.g. 1024 -> 1004
e.g. 2024 -> 1014

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int maxDiff(int num) {

string s = to_string(num);

const int n = s.length();

string n1(s);

string n2(s);

s += '#'; // append an unmatchable char to avoid out_of_bound.

int x = 0;

int y = 0;

while (x < n && (s[x] == '0' || s[x] == '1')) ++x;

while (y < n && s[y] == '9') ++y;

for (char& c : n1)

if (c == s[x]) c = x ? '0' : '1';

for (char& c : n2)

if (c == s[y]) c = '9';

return stoi(n2) - stoi(n1);

}

};

花花酱 LeetCode 1431. Kids With the Greatest Number of Candies

By zxi on May 3, 2020

Given the array candies and the integer extraCandies, where candies[i] represents the number of candies that the ith kid has.

For each kid check if there is a way to distribute extraCandies among the kids such that he or she can have the greatest number of candies among them. Notice that multiple kids can have the greatest number of candies.

Example 1:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: 
Kid 1 has 2 candies and if he or she receives all extra candies (3) will have 5 candies --- the greatest number of candies among the kids. 
Kid 2 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids. 
Kid 3 has 5 candies and this is already the greatest number of candies among the kids. 
Kid 4 has 1 candy and even if he or she receives all extra candies will only have 4 candies. 
Kid 5 has 3 candies and if he or she receives at least 2 extra candies will have the greatest number of candies among the kids.

Example 2:

Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false] 
Explanation: There is only 1 extra candy, therefore only kid 1 will have the greatest number of candies among the kids regardless of who takes the extra candy.

Example 3:

Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]

Constraints:

2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

Solution: Finding max

Find the maximum candies that a kid has.

ans[i] = (candies[i] + extra) >= max_candies

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

C++

// Author: Huahua

class Solution {

public:

vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {

const int threshold = *max_element(begin(candies), end(candies));

vector<bool> ans(candies.size());

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

ans[i] = (candies[i] + extraCandies) >= threshold;

return ans;

}

};

Python

# Author: Huahua

class Solution:

def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:

m = max(candies)

return [c + extraCandies >= m for c in candies]

花花酱 LeetCode 1425. Constrained Subset Sum

By zxi on April 26, 2020

Given an integer array nums and an integer k, return the maximum sum of a non-empty subset of that array such that for every two consecutive integers in the subset, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subset of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subset is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subset must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subset is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

Solution: DP / Sliding window / monotonic queue

dp[i] := max sum of a subset that include nums[i]
dp[i] := max(dp[i-1], dp[i-2], …, dp[i-k-1], 0) + nums[i]

C++

// Author: Huahua

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

multiset<int> s{INT_MIN};

int ans = INT_MIN;

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

if (i > k) s.erase(s.equal_range(dp[i - k - 1]).first);

dp[i] = max(*rbegin(s), 0) + nums[i];

s.insert(dp[i]);

ans = max(ans, dp[i]);

}

return ans;

}

};

Use a monotonic queue to track the maximum of a sliding window dp[i-k-1] ~ dp[i-1].

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

C++

// Author: Huahua 184 ms

class Solution {

public:

int constrainedSubsetSum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> dp(n);

deque<int> q;

int ans = INT_MIN;

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

if (i > k && q.front() == i - k - 1)

q.pop_front();

dp[i] = (q.empty() ? 0 : max(dp[q.front()], 0))

+ nums[i];

while (!q.empty() && dp[i] >= dp[q.back()])

q.pop_back();

q.push_back(i);

ans = max(ans, dp[i]);

}

return ans;

}

};

花花酱 LeetCode 1424. Diagonal Traverse II

By zxi on April 26, 2020

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i].length <= 10^5
1 <= nums[i][j] <= 10^9
There at most 10^5 elements in nums.

Solution: Hashtable

Use diagonal index (i + j) as key.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> findDiagonalOrder(vector<vector<int>>& nums) {

vector<vector<int>> m;

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

for (int j = 0; j < nums[i].size(); ++j) {

if (m.size() <= i + j) m.push_back({});

m[i + j].push_back(nums[i][j]);

}

vector<int> ans;

for (const auto& d : m)

ans.insert(end(ans), rbegin(d), rend(d));

return ans;

}

};

Python

# Author: Huahua

class Solution:

def findDiagonalOrder(self, nums):

m = []

for i, row in enumerate(nums):

for j, v in enumerate(row):

if i + j >= len(m): m.append([])

m[i+j].append(v)

return [v for d in m for v in reversed(d)]

Huahua's Tech Road

LeetCode 1433. Check If a String Can Break Another String

Solution 1: Sort and compare

C++

Solution 2: Counting Sort

C++

花花酱 LeetCode 1432. Max Difference You Can Get From Changing an Integer

Solution 1: Brute Force

C++

Solution 2: Greedy

C++

花花酱 LeetCode 1431. Kids With the Greatest Number of Candies

Solution: Finding max

C++

Python

花花酱 LeetCode 1425. Constrained Subset Sum

Solution: DP / Sliding window / monotonic queue

C++

C++

花花酱 LeetCode 1424. Diagonal Traverse II

Solution: Hashtable

C++

Python