Dmitrii Volyx

22. Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. Example 1: Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"] Example 2: Input: n = 1 Output: ["()"] Constraints: 1 <= n <= 8 Solution class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); backtracking("(", 1, 0, n, res); return res; } void backtracking(String s, int open, int closed, int n, List<String> res) { if (open + closed == 2 * n) { res.add(s); return; } if (open < n) backtracking(s + "(", open + 1, closed, n, res); if (open > closed) backtracking(s + ")", open, closed + 1, n, res); } }

90. Subsets II Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]] Example 2: Input: nums = [0] Output: [[],[0]] Constraints: 1 <= nums.length <= 10 -10 <= nums[i] <= 10 Solution class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> current = new ArrayList<>(); Arrays.sort(nums); backtrack(nums, 0, current, res); return res; } void backtrack(int[] nums, int index, List<Integer> current, List<List<Integer>> res) { res.add(new ArrayList<>(current)); for (int i = index; i < nums.length; i++) { if (i > index && nums[i - 1] == nums[i]) { continue; } current.add(nums[i]); backtrack(nums, i + 1, current, res); current.remove(current.size() - 1); } } }

343. Integer Break Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get. Example 1: Input: n = 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1. Example 2: Input: n = 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Constraints: ...

46. Permutations Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Example 3: Input: nums = [1] Output: [[1]] Constraints: 1 <= nums.length <= 6 -10 <= nums[i] <= 10 All the integers of nums are unique. Solution class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); backtrack(res, nums, 0); return res; } void backtrack(List<List<Integer>> res, int[] nums, int index) { if (index == nums.length - 1) { res.add(toList(nums)); return; } for (int i = index; i < nums.length; i++) { swap(nums, i, index); backtrack(res, nums, index + 1); swap(nums, i, index); } } List<Integer> toList(int[] nums) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { list.add(nums[i]); } return list; } void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } Solution 2021-11-22 class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); permuteAt(0, nums, res); return res; } void permuteAt(int i, int[] nums, List<List<Integer>> res) { if (i == nums.length - 1) { res.add(toList(nums)); return; } for (int j = i; j < nums.length; j++) { swap(i, j, nums); permuteAt(i + 1, nums, res); swap(i, j, nums); } } void swap(int i, int j, int[] arr) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } List<Integer> toList(int[] values) { List<Integer> res = new ArrayList<>(values.length); for (int val : values) { res.add(val); } return res; } }

78. Subsets Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: Input: nums = [0] Output: [[],[0]] Constraints: 1 <= nums.length <= 10 -10 <= nums[i] <= 10 All the numbers of nums are unique. Solution class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> subsets = new ArrayList<>(); int n = nums.length; for (int i = (int) Math.pow(2, n); i < (int) Math.pow(2, n + 1); i++) { // generate bitmasks from 00.000 to 111..111 String bitmask = Integer.toBinaryString(i).substring(1); List<Integer> curr = new ArrayList<>(); for (int j = 0; j < n; j++) { if (bitmask.charAt(j) == '1') curr.add(nums[j]); } subsets.add(curr); } return subsets; } public List<List<Integer>> subsets3(int[] nums) { List<List<Integer>> subsets = new ArrayList<>(); List<Integer> current = new ArrayList<>(); dfs(0, nums, current, subsets); return subsets; } void dfs(int index, int[] nums, List<Integer> current, List<List<Integer>> subsets) { if (index == nums.length) { subsets.add(new ArrayList<>(current)); return; } current.add(nums[index]); dfs(index + 1, nums, current, subsets); current.remove(current.size() - 1); dfs(index + 1, nums, current, subsets); } public List<List<Integer>> subsets2(int[] nums) { List<List<Integer>> subsets = new ArrayList<>(); List<Integer> current = new ArrayList<>(); generateSubsets(0, nums, current, subsets); return subsets; } void generateSubsets(int index, int[] nums, List<Integer> current, List<List<Integer>> subsets) { subsets.add(new ArrayList<>(current)); for (int i = index; i < nums.length; i++) { current.add(nums[i]); generateSubsets(i + 1, nums, current, subsets); current.remove(current.size() - 1); } } } Solution 2021-11-22 class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> curr = new ArrayList<>(); dfs(0, nums, res, curr); return res; } void dfs(int index, int[] nums, List<List<Integer>> res, List<Integer> curr) { if (index == nums.length) { res.add(List.copyOf(curr)); return; } curr.add(nums[index]); dfs(index + 1, nums, res, curr); curr.remove(curr.size() - 1); dfs(index + 1, nums, res, curr); } }

1876. Substrings of Size Three with Distinct Characters A string is good if there are no repeated characters. Given a string s​​​​​, return the number of good substrings of length three in s​​​​​​. Note that if there are multiple occurrences of the same substring, every occurrence should be counted. A substring is a contiguous sequence of characters in a string. Example 1: Input: s = "xyzzaz" Output: 1 Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz". The only good substring of length 3 is "xyz". Example 2: Input: s = "aababcabc" Output: 4 Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc". The good substrings are "abc", "bca", "cab", and "abc". Constraints: ...

1877. Minimize Maximum Pair Sum in Array The pair sum of a pair (a,b) is equal to a + b. The maximum pair sum is the largest pair sum in a list of pairs. For example, if we have pairs (1,5), (2,3), and (4,4), the maximum pair sum would be max(1+5, 2+3, 4+4) = max(6, 5, 8) = 8. Given an array nums of even length n, pair up the elements of nums into n / 2 pairs such that: ...

1878. Get Biggest Three Rhombus Sums in a Grid You are given an m x n integer matrix grid​​​. A rhombus sum is the sum of the elements that form the border of a regular rhombus shape in grid​​​. The rhombus must have the shape of a square rotated 45 degrees with each of the corners centered in a grid cell. Below is an image of four valid rhombus shapes with the corresponding colored cells that should be included in each rhombus sum: ...

221. Maximal Square Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. Example 1: Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] Output: 4 Example 2: Input: matrix = [["0","1"],["1","0"]] Output: 1 Example 3: Input: matrix = [["0"]] Output: 0 Constraints: m == matrix.length n == matrix[i].length 1 <= m, n <= 300 matrix[i][j] is ‘0’ or ‘1’. Solution class Solution { public int maximalSquare(char[][] matrix) { int n = matrix.length; int m = matrix[0].length; int[][] dp = new int[n][m]; int max = 0; for (int j = 0; j < m; j++) { dp[0][j] = matrix[0][j] == '0' ? 0 : 1; max = Math.max(dp[0][j], max); } for (int i = 0; i < n; i++) { dp[i][0] = matrix[i][0] == '0' ? 0: 1; max = Math.max(dp[i][0], max); } for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { if (matrix[i][j] == '0') { dp[i][j] = 0; } else { dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1; } max = Math.max(dp[i][j], max); } } return max * max; } int min(int a, int b, int c) { return Math.min(a, Math.min(b,c)); } }

1852. Distinct Numbers in Each Subarray Given an integer array nums and an integer k, you are asked to construct the array ans of size n-k+1 where ans[i] is the number of distinct numbers in the subarray nums[i:i+k-1] = [nums[i], nums[i+1], …, nums[i+k-1]]. Return the array ans. Example 1: Input: nums = [1,2,3,2,2,1,3], k = 3 Output: [3,2,2,2,3] Explanation: The number of distinct elements in each subarray goes as follows: - nums[0:2] = [1,2,3] so ans[0] = 3 - nums[1:3] = [2,3,2] so ans[1] = 2 - nums[2:4] = [3,2,2] so ans[2] = 2 - nums[3:5] = [2,2,1] so ans[3] = 2 - nums[4:6] = [2,1,3] so ans[4] = 3 Example 2: Input: nums = [1,1,1,1,2,3,4], k = 4 Output: [1,2,3,4] Explanation: The number of distinct elements in each subarray goes as follows: - nums[0:3] = [1,1,1,1] so ans[0] = 1 - nums[1:4] = [1,1,1,2] so ans[1] = 2 - nums[2:5] = [1,1,2,3] so ans[2] = 3 - nums[3:6] = [1,2,3,4] so ans[3] = 4 Constraints: ...