leetcode 1520 - Maximum Number of Non-Overlapping Substrings

https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/
https://leetcode.com/problems/maximum-number-of-non-overlapping-substrings/discuss/743223/C%2B%2BJava-Greedy-O(n)

Given a string s of lowercase letters, you need to find the maximum number of non-empty substrings of s that meet the following conditions:

The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.

Notice that you can return the substrings in any order.

Example 1:

Input: s = “adefaddaccc”
Output: [“e”,”f”,”ccc”]
Explanation: The following are all the possible substrings that meet the conditions:
[
“adefaddaccc”
“adefadda”,
“ef”,
“e”,
“f”,
“ccc”,
]
If we choose the first string, we cannot choose anything else and we’d get only 1. If we choose “adefadda”, we are left with “ccc” which is the only one that doesn’t overlap, thus obtaining 2 substrings. Notice also, that it’s not optimal to choose “ef” since it can be split into two. Therefore, the optimal way is to choose [“e”,”f”,”ccc”] which gives us 3 substrings. No other solution of the same number of substrings exist.
Example 2:

Input: s = “abbaccd”
Output: [“d”,”bb”,”cc”]
Explanation: Notice that while the set of substrings [“d”,”abba”,”cc”] also has length 3, it’s considered incorrect since it has larger total length.

Constraints:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
vector<string> maxNumOfSubstrings(string s) {
vector<int> left_idx(26, -1);
vector<int> right_idx(26, -1);
int size = s.size();

for (int i = 0; i < size; i++) {
int c = s[i] - 'a';
if (left_idx[c] == -1)
left_idx[c] = i;
right_idx[c] = i;
}

vector<string> result;
int prev_right_idx;

for (int i = 0; i < size; i++) {
int c = s[i] - 'a';

if (left_idx[c] == i) {
int j = get_right_idx(s, i, left_idx, right_idx);
if (j != -1) {
if (result.empty() || j > prev_right_idx)
result.push_back(s.substr(i, j - i + 1));
else
result.back() = s.substr(i, j - i + 1);

prev_right_idx = j;
}
}
}

return result;
}

int get_right_idx(string &s, int i, vector<int> &left_idx,
vector<int> &right_idx) {
int right = right_idx[s[i] - 'a'];

for (int left = i; left <= right; left++) {
int c = s[left] - 'a';
if (left_idx[c] < i)
return -1;
right = max(right, right_idx[c]);
}

return right;
}
};

leetcode 1591 - Strange Printer II

https://leetcode.com/problems/strange-printer-ii/
https://leetcode.com/problems/strange-printer-ii/discuss/854151/C%2B%2B-O(n3)-solution-checking-cycle-in-dependency-graph

There is a strange printer with the following two special requirements:

On each turn, the printer will print a solid rectangular pattern of a single color on the grid. This will cover up the existing colors in the rectangle.
Once the printer has used a color for the above operation, the same color cannot be used again.
You are given a m x n matrix targetGrid, where targetGrid[row][col] is the color in the position (row, col) of the grid.

Return true if it is possible to print the matrix targetGrid, otherwise, return false.

Example 1:

Input: targetGrid = [[1,1,1,1],[1,2,2,1],[1,2,2,1],[1,1,1,1]]
Output: true
Example 2:

Input: targetGrid = [[1,1,1,1],[1,1,3,3],[1,1,3,4],[5,5,1,4]]
Output: true
Example 3:

Input: targetGrid = [[1,2,1],[2,1,2],[1,2,1]]
Output: false
Explanation: It is impossible to form targetGrid because it is not allowed to print the same color in different turns.
Example 4:

Input: targetGrid = [[1,1,1],[3,1,3]]
Output: false

Constraints:

m == targetGrid.length
n == targetGrid[i].length
1 <= m, n <= 60
1 <= targetGrid[row][col] <= 60

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
bool isPrintable(vector<vector<int>>& targetGrid) {
int row = targetGrid.size();
int col = targetGrid[0].size();
vector<unordered_set<int>> edges(61);

for (int i = 1; i <= 60; i++) {
int minx = INT_MAX, maxx = INT_MIN, miny = INT_MAX, maxy = INT_MIN;

for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (targetGrid[r][c] == i) {
minx = min(minx, r);
maxx = max(maxx, r);
miny = min(miny, c);
maxy = max(maxy, c);
}
}
}

for (int r = minx; r <= maxx; r++) {
for (int c = miny; c <= maxy; c++) {
if (targetGrid[r][c] != i) {
edges[i].insert(targetGrid[r][c]);
}
}
}
}

vector<int> seen(61, 0);

for (int i = 1; i <= 60; i++) {
if (seen[i] == 0 && hasCycle(i, edges, seen) == true)
return false;
}

return true;
}

bool hasCycle(int i, vector<unordered_set<int>> &edges, vector<int> &seen) {
if (seen[i] == 1)
return true;

seen[i] = 1;
for (int k : edges[i]) {
if (hasCycle(k, edges, seen))
return true;
}
seen[i] = 2;

return false;
}
};

leetcode 664 - Strange Printer

https://leetcode.com/problems/strange-printer/
https://leetcode.com/problems/strange-printer/discuss/106810/Java-O(n3)-DP-Solution-with-Explanation-and-Simple-Optimization

There is a strange printer with the following two special requirements:

The printer can only print a sequence of the same character each time.
At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.
Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:
Input: “aaabbb”
Output: 2
Explanation: Print “aaa” first and then print “bbb”.
Example 2:
Input: “aba”
Output: 2
Explanation: Print “aaa” first and then print “b” from the second place of the string, which will cover the existing character ‘a’.
Hint: Length of the given string will not exceed 100.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
int strangePrinter(string s) {
int size = s.size();

if (size == 0) return 0;

vector<vector<int>> memo(size, vector<int>(size, -1));

return strangePrinter(s, 0, size - 1, memo);
}

int strangePrinter(string &s, int i, int j, vector<vector<int>> &memo) {
if (i == j) return 1;

if (memo[i][j] != -1) return memo[i][j];

int prints = INT_MAX;

for (int k = i; k <= j - 1; k++) {
prints = min(prints, strangePrinter(s, i, k, memo) +
strangePrinter(s, k+1, j, memo) - (s[k] == s[j]));
}

memo[i][j] = prints;

return prints;
}
};

leetcode 1722 - Minimize Hamming Distance After Swap Operations

https://leetcode.com/problems/minimize-hamming-distance-after-swap-operations/

You are given two integer arrays, source and target, both of length n. You are also given an array allowedSwaps where each allowedSwaps[i] = [ai, bi] indicates that you are allowed to swap the elements at index ai and index bi (0-indexed) of array source. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, source and target, is the number of positions where the elements are different. Formally, it is the number of indices i for 0 <= i <= n-1 where source[i] != target[i] (0-indexed).

Return the minimum Hamming distance of source and target after performing any amount of swap operations on array source.

Example 1:

Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: source can be transformed the following way:

  • Swap indices 0 and 1: source = [2,1,3,4]
  • Swap indices 2 and 3: source = [2,1,4,3]
    The Hamming distance of source and target is 1 as they differ in 1 position: index 3.
    Example 2:

Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation: There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.
Example 3:

Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0

Constraints:

n == source.length == target.length
1 <= n <= 10^5
1 <= source[i], target[i] <= 10^5
0 <= allowedSwaps.length <= 10^5
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
int minimumHammingDistance(vector<int>& source, vector<int>& target,
vector<vector<int>>& allowedSwaps) {
unordered_map<int, vector<int>> graph;

for (auto &p : allowedSwaps) {
graph[p[0]].push_back(p[1]);
graph[p[1]].push_back(p[0]);
}

unordered_set<int> seen;
int same = 0;

int size = source.size();
for (int i = 0; i < size; i++) {
if (graph.count(i) == 0) {
same += source[i] == target[i];
continue;
}
if (seen.count(i) > 0)
continue;

vector<int> indexs;

dfs(graph, i, seen, indexs);
same += count_same(source, target, indexs);
}

return size - same;
}

void dfs(unordered_map<int, vector<int>> &graph, int i,
unordered_set<int> &seen, vector<int> &indexs) {
if (seen.count(i))
return;

seen.insert(i);
indexs.push_back(i);

for (int j : graph[i])
dfs(graph, j, seen, indexs);
}

int count_same(vector<int>& source, vector<int>& target, vector<int> &indexs) {
int same = 0;
unordered_map<int, int> count;

for (int i : indexs) {
if (count[source[i]] < 0)
same++;
count[source[i]]++;

if (count[target[i]] > 0)
same++;
count[target[i]]--;
}

return same;
}
};

leetcode 1674 - Minimum Moves to Make Array Complementary

https://leetcode.com/problems/minimum-moves-to-make-array-complementary/
https://leetcode.com/problems/minimum-moves-to-make-array-complementary/discuss/952773/PythonJava-simple-O(max(n-k))-method

You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.

The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.

Return the minimum number of moves required to make nums complementary.

Example 1:

Input: nums = [1,2,4,3], limit = 4
Output: 1
Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.
Example 2:

Input: nums = [1,2,2,1], limit = 2
Output: 2
Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit.
Example 3:

Input: nums = [1,2,1,2], limit = 2
Output: 0
Explanation: nums is already complementary.

Constraints:

n == nums.length
2 <= n <= 10^5
1 <= nums[i] <= limit <= 10^5
n is even.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int minMoves(vector<int>& nums, int limit) {
vector<int> delta(2 * limit + 2, 0);
int n = nums.size();

for (int i = 0; i < n / 2; i++) {
int a = nums[i], b = nums[n - 1 - i];
delta[2] += 2;
delta[min(a, b) + 1]--;
delta[a + b]--;
delta[a + b + 1]++;
delta[max(a, b) + limit + 1]++;
}

int res = 2 * n, curr = 0;
for (int i = 2; i <= 2 * limit; i++) {
curr += delta[i];
res = min(res, curr);
}

return res;
}
};

leetcode 1685 - Sum of Absolute Differences in a Sorted Array

https://leetcode.com/problems/sum-of-absolute-differences-in-a-sorted-array/

You are given an integer array nums sorted in non-decreasing order.

Build and return an integer array result with the same length as nums such that result[i] is equal to the summation of absolute differences between nums[i] and all the other elements in the array.

In other words, result[i] is equal to sum(|nums[i]-nums[j]|) where 0 <= j < nums.length and j != i (0-indexed).

Example 1:

Input: nums = [2,3,5]
Output: [4,3,5]
Explanation: Assuming the arrays are 0-indexed, then
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4,
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3,
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5.
Example 2:

Input: nums = [1,4,6,8,10]
Output: [24,15,13,15,21]

Constraints:

2 <= nums.length <= 10^5
1 <= nums[i] <= nums[i + 1] <= 10^4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
int size = nums.size();
vector<int> result(size, 0);

int sum = 0;
for (int i = 1; i < size; i++) {
sum += i * abs(nums[i] - nums[i-1]);
result[i] = sum;
}

sum = 0;
for (int i = size - 2; i >= 0; i--) {
sum += (size - i - 1) * abs(nums[i] - nums[i+1]);
result[i] += sum;
}

return result;
}
};

leetcode 1404 - Number of Steps to Reduce a Number in Binary Representation to One

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/
https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/discuss/564287/C%2B%2BJava-O(n)

Given a number s in their binary representation. Return the number of steps to reduce it to 1 under the following rules:

If the current number is even, you have to divide it by 2.

If the current number is odd, you have to add 1 to it.

It’s guaranteed that you can always reach to one for all testcases.

Example 1:

Input: s = “1101”
Output: 6
Explanation: “1101” corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14.
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.
Step 5) 4 is even, divide by 2 and obtain 2.
Step 6) 2 is even, divide by 2 and obtain 1.
Example 2:

Input: s = “10”
Output: 1
Explanation: “10” corressponds to number 2 in their decimal representation.
Step 1) 2 is even, divide by 2 and obtain 1.
Example 3:

Input: s = “1”
Output: 0

Constraints:

1 <= s.length <= 500
s consists of characters ‘0’ or ‘1’
s[0] == ‘1’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int numSteps(string s) {
int size = s.size();
int total = 0;
int carry = 0;

for (int i = size - 1; i > 0; i--) {
total++;

if (s[i] - '0' + carry == 1) {
carry = 1;
total++;
}
}

return total + carry;
}
};

leetcode 1358 - Number of Substrings Containing All Three Characters

https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/

Given a string s consisting only of characters a, b and c.

Return the number of substrings containing at least one occurrence of all these characters a, b and c.

Example 1:

Input: s = “abcabc”
Output: 10
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “abc”, “abca”, “abcab”, “abcabc”, “bca”, “bcab”, “bcabc”, “cab”, “cabc” and “abc” (again).
Example 2:

Input: s = “aaacb”
Output: 3
Explanation: The substrings containing at least one occurrence of the characters a, b and c are “aaacb”, “aacb” and “acb”.
Example 3:

Input: s = “abc”
Output: 1

Constraints:

3 <= s.length <= 5 x 10^4
s only consists of a, b or c characters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
int numberOfSubstrings(string s) {
int size = s.size();

return ((long)size * (size + 1)) / 2 - noneABC(s);
}

int noneABC(string &s) {
int size = s.size();
vector<int> count(3, 0);
int total = 0;

int i = 0;
for (int j = 0; j < size; j++) {
int k = s[j] - 'a';
count[k]++;

while (count[0] >= 1 && count[1] >= 1 && count[2] >= 1) {
k = s[i++] - 'a';
count[k]--;
}

total += j - i + 1;
}

return total;
}
};

class Solution {
public:
int numberOfSubstrings(string s) {
int size = s.size();
int total = 0;

int count[3] = {0, 0, 0};
int i = 0;
for (int j = 0; j < size; j++) {
int k = s[j] - 'a';
count[k]++;

while (count[0] && count[1] && count[2]) {
k = s[i++] - 'a';
count[k]--;
}

total += i;
}

return total;
}
};

leetcode 1248 - Count Number of Nice Subarrays

https://leetcode.com/problems/count-number-of-nice-subarrays/

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.
Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

Constraints:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int size = nums.size();
unordered_map<int, int> count;
int total = 0;
int odd = 0;

count[0] = 1;

for (int i = 0; i < size; i++) {
odd += nums[i] % 2;

total += count[odd - k];
count[odd]++;

for (int i = 0; i < odd - k; i++) {
if (count.count(i) == 0)
break;
count.erase(i);
}
}

return total;
}
};

//Space O(1)
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
return atMostK(nums, k) - atMostK(nums, k-1);
}

int atMostK(vector<int>& nums, int k) {
int size = nums.size();
int odd = 0;
int total = 0;

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

while (odd > k) {
odd -= nums[i++] % 2;
}

total += j - i + 1;
}

return total;
}
};

leetcode 1234 - Replace the Substring for Balanced String

https://leetcode.com/problems/replace-the-substring-for-balanced-string/

You are given a string containing only 4 kinds of characters ‘Q’, ‘W’, ‘E’ and ‘R’.

A string is said to be balanced if each of its characters appears n/4 times where n is the length of the string.

Return the minimum length of the substring that can be replaced with any other string of the same length to make the original string s balanced.

Return 0 if the string is already balanced.

Example 1:

Input: s = “QWER”
Output: 0
Explanation: s is already balanced.
Example 2:

Input: s = “QQWE”
Output: 1
Explanation: We need to replace a ‘Q’ to ‘R’, so that “RQWE” (or “QRWE”) is balanced.
Example 3:

Input: s = “QQQW”
Output: 2
Explanation: We can replace the first “QQ” to “ER”.
Example 4:

Input: s = “QQQQ”
Output: 3
Explanation: We can replace the last 3 ‘Q’ to make s = “QWER”.

Constraints:

1 <= s.length <= 10^5
s.length is a multiple of 4
s contains only ‘Q’, ‘W’, ‘E’ and ‘R’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
int balancedString(string s) {
//Q W E R
int size = s.size();
unordered_map<char, int> cnt;

for (char c : s)
cnt[c]++;

string word = "QWER";
for (char c : word) {
if (cnt[c] > size /4)
cnt[c] -= size / 4;
else
cnt.erase(c);
}

if (cnt.size() == 0) return 0;

int min_len = INT_MAX;
int i = 0;

int found = 0;

for (int j = 0; j < size; j++) {
char c = s[j];

if (cnt.count(c) > 0) {
if (--cnt[c] == 0)
found++;
}

while (found == cnt.size()) {
min_len = min(min_len, j - i + 1);
c = s[i++];
if (cnt.count(c) > 0) {
if (cnt[c]++ == 0)
found--;
}
}

}

return min_len;
}
};