2744. Find Maximum Number of String Pairs
You are given a 0-indexed array words consisting of distinct strings.
The string words[i] can be paired with the string words[j] if:
- The string words[i] is equal to the reversed string of words[j].
- 0 <= i < j < words.length.
Return the maximum number of pairs that can be formed from the array words.
Note that each string can belong in at most one pair.
Example:
Input: words = ["cd","ac","dc","ca","zz"]
Output: 2
class Solution {
public int maximumNumberOfStringPairs(String[] words) {
Set<String> set = new HashSet<>();
int res = 0;
for (String w : words) {
String r = reverse(w);
if (set.contains(r)) {
++res;
}
set.add(w);
}
return res;
}
private String reverse(String w) {
StringBuilder sb = new StringBuilder(w);
return sb.reverse().toString();
}
}2745. Construct the Longest New String
You are given three integers x, y, and z.
You have x strings equal to "AA", y strings equal to "BB", and z strings equal to "AB". You want to choose some (possibly all or none) of these strings and concactenate them in some order to form a new string. This new string must not contain "AAA" or "BBB" as a substring.
Return the maximum possible length of the new string.
A substring is a contiguous non-empty sequence of characters within a string.
Example
Input: x = 2, y = 5, z = 1
Output: 12
class Solution {
public int longestString(int x, int y, int z) {
return (Math.min(x, y) * 2 + (x != y ? 1 : 0) + z) << 1;
}
}
2746. Decremental String Concatenation
You are given a 0-indexed array words containing n strings.
Let's define a join operation join(x, y) between two strings x and y as concatenating them into xy. However, if the last character of x is equal to the first character of y, one of them is deleted.
For example join("ab", "ba") = "aba" and join("ab", "cde") = "abcde".
You are to perform n - 1 join operations. Let str0 = words[0]. Starting from i = 1 up to i = n - 1, for the ith operation, you can do one of the following:
- Make stri = join(stri - 1, words[i])
- Make stri = join(words[i], stri - 1)
Your task is to minimize the length of str_(n - 1).
Return an integer denoting the minimum possible length of str_(n - 1).
Example：
words = ["aa","ab","bc"]
Output: 4
class Solution {
public int minimizeConcatenatedLength(String[] words) {
int[][] mem = new int[26][26];
mem[words[0].charAt(0) - 'a'][words[0].charAt(words[0].length() - 1) - 'a'] = words[0].length();
for (int i = 1; i < words.length; ++i) {
int[][] nextMem = new int[26][26];
int f = words[i].charAt(0) - 'a', l = words[i].charAt(words[i].length() - 1) - 'a';
for (int j = 0; j < 26; ++j) {
for (int k = 0; k < 26; ++k) {
if (mem[j][k] != 0) {
nextMem[j][l] = Math.min(nextMem[j][l] == 0 ? Integer.MAX_VALUE : nextMem[j][l], mem[j][k] + words[i].length() - (k == f ? 1 : 0));
nextMem[f][k] = Math.min(nextMem[f][k] == 0 ? Integer.MAX_VALUE : nextMem[f][k], mem[j][k] + words[i].length() - (l == j ? 1 : 0));
}
}
}
mem = nextMem;
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (mem[i][j] != 0) res = Math.min(res, mem[i][j]);
}
}
return res;
}
}2747. Count Zero Request Servers
You are given an integer n denoting the total number of servers and a 2D 0-indexed integer array logs, where logs[i] = [server_id, time] denotes that the server with id server_id received a request at time time.
You are also given an integer x and a 0-indexed integer array queries.
Return a 0-indexed integer array arr of length queries.length where arr[i] represents the number of servers that did not receive any requests during the time interval [queries[i] - x, queries[i]].
Note that the time intervals are inclusive.
Example：
Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
Output: [1,2]
class Solution {
public int[] countServers(int n, int[][] logs, int x, int[] queries) {
Arrays.sort(logs, (a, b) -> (a[1] - b[1]));
Integer[] querySort = new Integer[queries.length];
for (int i = 0; i < queries.length; ++i) {
querySort[i] = i;
}
Arrays.sort(querySort, (a, b) -> (queries[a] - queries[b]));
HashMap<Integer, Integer> mem = new HashMap<>();
int[] res = new int[queries.length];
int left = 0, right = 0;
for (int i : querySort) {
int q = queries[i];
while (right < logs.length && logs[right][1] <= q) {
mem.put(logs[right][0], mem.getOrDefault(logs[right][0], 0) + 1);
++right;
}
while (left < logs.length && logs[left][1] < q - x) {
int tmp = mem.get(logs[left][0]);
if (tmp == 1) {
mem.remove(logs[left][0]);
} else {
mem.put(logs[left][0], tmp - 1);
}
++left;
}
res[i] = n - mem.size();
}
return res;
}
}2748. Number of Beautiful Pairs
You are given a 0-indexed integer array nums. A pair of indices i, j where 0 <= i < j < nums.length is called beautiful if the first digit of nums[i] and the last digit of nums[j] are coprime.
Return the total number of beautiful pairs in nums.
Two integers x and y are coprime if there is no integer greater than 1 that divides both of them. In other words, x and y are coprime if gcd(x, y) == 1, where gcd(x, y) is the greatest common divisor of x and y.
Example
Input: nums = [2,5,1,4]
Output: 5
class Solution {
public int countBeautifulPairs(int[] nums) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = i + 1; j < nums.length; ++j) {
if (gcd(nums[i], nums[j]) == 1) {
++res;
}
}
}
return res;
}
private int gcd(int x, int y) {
while (y != 0) {
int tmp = x % y;
x = y;
y = tmp;
}
return x;
}
}2749. Minimum Operations to Make the Integer Zero
You are given two integers num1 and num2.
In one operation, you can choose integer i in the range [0, 60] and subtract 2i + num2 from num1.
Return the integer denoting the minimum number of operations needed to make num1 equal to 0.
If it is impossible to make num1 equal to 0, return -1.
Example
Input: num1 = 3, num2 = -2
Output: 3
class Solution {
public int makeTheIntegerZero(int num1, int num2) {
long add = num1 - num2;
for (int i = 1; i < 100; ++i) {
if (add < i) break;
if (zeroTime(add) <= i) {
return i;
}
add -= num2;
}
return -1;
}
private int zeroTime(long num) {
int res = 0;
while (num > 0) {
res += (num % 2);
num /= 2;
}
return res;
}
}2750. Ways to Split Array Into Good Subarrays
You are given a binary array nums.
A subarray of an array is good if it contains exactly one element with the value 1.
Return an integer denoting the number of ways to split the array nums into good subarrays. As the number may be too large, return it modulo 109 + 7.
A subarray is a contiguous non-empty sequence of elements within an array.
Example
Input: nums = [0,1,0,0,1]
Output: 3
class Solution {
private static final int mod = 1_000_000_007;
public int numberOfGoodSubarraySplits(int[] nums) {
long res = 1;
List<Integer> onePos = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == 1) {
onePos.add(i);
}
}
if (onePos.isEmpty()) return 0;
for (int i = 0; i + 1 < onePos.size(); ++i) {
int cur = onePos.get(i), next = onePos.get(i + 1);
res = (res * (next - cur)) % mod;
}
return (int) res;
}
}2751. Robot Collisions
There are n 1-indexed robots, each having a position on a line, health, and movement direction.
You are given 0-indexed integer arrays positions, healths, and a string directions (directions[i] is either 'L' for left or 'R' for right). All integers in positions are unique.
All robots start moving on the line simultaneously at the same speed in their given directions. If two robots ever share the same position while moving, they will collide.
If two robots collide, the robot with lower health is removed from the line, and the health of the other robot decreases by one. The surviving robot continues in the same direction it was going. If both robots have the same health, they are both removed from the line.
Your task is to determine the health of the robots that survive the collisions, in the same order that the robots were given, i.e. final heath of robot 1 (if survived), final health of robot 2 (if survived), and so on. If there are no survivors, return an empty array.
Return an array containing the health of the remaining robots (in the order they were given in the input), after no further collisions can occur.
Note: The positions may be unsorted.
Example
Input: positions = [5,4,3,2,1], healths = [2,17,9,15,10], directions = "RRRRR"
Output: [2,17,9,15,10]
class Solution {
public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
int len = positions.length;
Integer[] sort = new Integer[len];
for (int i = 0; i < len; ++i) {
sort[i] = i;
}
Arrays.sort(sort, (a, b) -> (positions[a] - positions[b]));
Stack<int[]> right = new Stack<>();
List<int[]> buffer = new ArrayList<>();
for (int i : sort) {
if (directions.charAt(i) == 'R') {
right.push(new int[]{i, healths[i]});
} else {
int cur = healths[i];
while (!right.isEmpty() && right.peek()[1] < cur) {
cur -= 1;
right.pop();
}
if (right.isEmpty()) {
buffer.add(new int[]{i, cur});
} else {
int[] tmp = right.pop();
if (tmp[1] > cur) {
tmp[1] -= 1;
right.push(tmp);
}
}
}
}
for (int[] r : right) {
buffer.add(r);
}
Collections.sort(buffer, (a, b) -> (a[0] - b[0]));
List<Integer> res = new ArrayList<>();
for (int[] i : buffer) {
res.add(i[1]);
}
return res;
}
}2760. Longest Even Odd Subarray With Threshold
TYou are given a 0-indexed integer array nums and an integer threshold.
Find the length of the longest subarray of nums starting at index l and ending at index r (0 <= l <= r < nums.length) that satisfies the following conditions:
- nums[l] % 2 == 0
- For all indices i in the range [l, r - 1], nums[i] % 2 != nums[i + 1] % 2
- For all indices i in the range [l, r], nums[i] <= threshold
Return an integer denoting the length of the longest such subarray.
Note: A subarray is a contiguous non-empty sequence of elements within an array.
Example
Input: nums = [3,2,5,4], threshold = 5
Output: 3
class Solution {
public int longestAlternatingSubarray(int[] nums, int threshold) {
int res = 0;
for (int i = 0; i < nums.length; ++i) {
for (int j = i; j < nums.length; ++j) {
if (isValid(nums, i, j, threshold)) {
res = Math.max(res, j - i + 1);
}
}
}
return res;
}
private boolean isValid(int[] nums, int st, int ed, int threshold) {
if (nums[st] % 2 != 0 || nums[ed] > threshold) {
return false;
}
for (int i = st; i < ed; ++i) {
if (nums[i] % 2 == nums[i + 1] % 2) {
return false;
}
if (nums[i] > threshold) {
return false;
}
}
return true;
}
}2761. Prime Pairs With Target Sum
You are given an integer n. We say that two integers x and y form a prime number pair if:
- 1 <= x <= y <= n
- x + y == n
- x and y are prime numbers
Return the 2D sorted list of prime number pairs [xi, yi]. The list should be sorted in increasing order of xi. If there are no prime number pairs at all, return an empty array.
Note: A prime number is a natural number greater than 1 with only two factors, itself and 1.
Example
Input: n = 10
Output: [[3,7],[5,5]]
class Solution {
public List<List<Integer>> findPrimePairs(int n) {
List<List<Integer>> res = new ArrayList<>();
for (int i = 2; i <= n - i; ++i) {
if (isPrime(i) && isPrime(n - i)) {
List<Integer> tmp = new ArrayList<>();
tmp.add(i);
tmp.add(n - i);
res.add(tmp);
}
}
return res;
}
private boolean isPrime(int n) {
for (int j = 2; j * j <= n; ++j) {
if (n % j == 0) {
return false;
}
}
return true;
}
}2762. Continuous Subarrays
You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:
- Let i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= i1, i2 <= j, 0 <= |nums[i1] - nums[i2]| <= 2.
Return the total number of continuous subarrays.
A subarray is a contiguous non-empty sequence of elements within an array.
Example
Input: nums = [5,4,2,4]
Output: 8
class Solution {
public long continuousSubarrays(int[] nums) {
long res = 0;
int st = 0, ed = 0;
TreeMap<Integer, Integer> count = new TreeMap<>();
while (ed < nums.length) {
count.put(nums[ed], count.getOrDefault(nums[ed], 0) + 1);
while (nums[ed] - count.firstKey() > 2 || count.lastKey() - nums[ed] > 2) {
int tmp = count.get(nums[st]);
if (tmp == 1) {
count.remove(nums[st]);
} else {
count.put(nums[st], tmp - 1);
}
++st;
}
++ed;
res = res + (ed - st);
}
return res;
}
}
2763. Sum of Imbalance Numbers of All Subarrays
The imbalance number of a 0-indexed integer array arr of length n is defined as the number of indices in sarr = sorted(arr) such that:
- 0 <= i < n - 1, and
- sarr[i+1] - sarr[i] > 1
Here, sorted(arr) is the function that returns the sorted version of arr.
Given a 0-indexed integer array nums, return the sum of imbalance numbers of all its subarrays.
A subarray is a contiguous non-empty sequence of elements within an array.
Example
Input: nums = [2,3,1,4]
Output: 3
class Solution {
public int sumImbalanceNumbers(int[] nums) {
int res = 0;
int[][] arr = new int[nums.length][];
for (int i = 0; i < nums.length; ++i) {
arr[i] = new int[]{nums[i], i};
}
for (int i = 0; i < nums.length; ++i) {
int subSum = 0;
TreeSet<int[]> set = new TreeSet<>((a, b) -> (a[0] == b[0] ? (a[1] - b[1]) : (a[0] - b[0])));
for (int j = i; j < nums.length; ++j) {
int[] lower = set.lower(arr[j]), higher = set.higher(arr[j]);
if (lower != null && higher != null && higher[0] - lower[0] > 1) {
--subSum;
}
if (lower != null && arr[j][0] - lower[0] > 1) {
++subSum;
}
if (higher != null && higher[0] - arr[j][0] > 1) {
++subSum;
}
res += subSum;
set.add(arr[j]);
}
}
return res;
}
}