Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Given a string s and an array of integers cost where cost[i] is the cost of deleting the ith character in s.

Return the minimum cost of deletions such that there are no two identical letters next to each other.

Notice that you will delete the chosen characters at the same time, in other words, after deleting a character, the costs of deleting other characters will not change.

Example 1:

Input: s = “abaac”, cost = [1,2,3,4,5] Output: 3 Explanation: Delete the letter “a” with cost 3 to get “abac” (String without two identical letters next to each other). Example 2:

Input: s = “abc”, cost = [1,2,3] Output: 0 Explanation: You don’t need to delete any character because there are no identical letters next to each other. Example 3:

Input: s = “aabaa”, cost = [1,2,3,4,1] Output: 2 Explanation: Delete the first and the last character, getting the string (“aba”).

Constraints:

s.length == cost.length 1 <= s.length, cost.length <= 10^5 1 <= cost[i] <= 10^4 s contains only lowercase English letters.

Today, the bookstore owner has a store open for customers.length minutes. Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy. If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0. When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3 Output: 16 Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

classSolution { public: vector<int> leader; vector<int> total; intlargestIsland(vector<vector<int>>& grid){ int row = grid.size(), col = grid[0].size(); int size = row * col; leader.resize(size); total.resize(size, 1); for (int i = 0; i < size; i++) { leader[i] = i; } vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; for (int r = 0; r < row; r++) { for (int c = 0; c < col; c++) { if (grid[r][c] == 1) { for (auto d : dirs) { int rr = r + d[0]; int cc = c + d[1]; if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0) continue; Union(find(r*row + c), find(rr*row + cc)); } } } } int max_island = 0; for (int r = 0; r < row; r++) { for (int c = 0; c < col; c++) { if (grid[r][c] == 0) { unordered_set<int> set; for (auto d : dirs) { int rr = r + d[0]; int cc = c + d[1]; if (rr < 0 || rr >= row || cc < 0 || cc >= col || grid[rr][cc] == 0) continue; set.insert(find(rr * row + cc)); } int cnt = 1; for (auto i : set) cnt += total[i]; max_island = max(max_island, cnt); } } } return max_island == 0 ? size : max_island; } intfind(int i){ if (leader[i] != i) leader[i] = find(leader[i]); return leader[i]; } voidUnion(int i, int j){ int x = leader[i]; int y = leader[j]; if (x == y) return; leader[x] = y; total[y] += total[x]; } };

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it’s guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0] Output: 0 Explanation: The head of the company is the only employee in the company. Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] Output: 1 Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all. The tree structure of the employees in the company is shown. Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1] Output: 21 Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute. The employee with id = 5 will inform the employee with id = 4 in 2 minutes. The employee with id = 4 will inform the employee with id = 3 in 3 minutes. The employee with id = 3 will inform the employee with id = 2 in 4 minutes. The employee with id = 2 will inform the employee with id = 1 in 5 minutes. The employee with id = 1 will inform the employee with id = 0 in 6 minutes. Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21. Example 4:

Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0] Output: 3 Explanation: The first minute the head will inform employees 1 and 2. The second minute they will inform employees 3, 4, 5 and 6. The third minute they will inform the rest of employees. Example 5:

1 <= n <= 10^5 0 <= headID < n manager.length == n 0 <= manager[i] < n manager[headID] == -1 informTime.length == n 0 <= informTime[i] <= 1000 informTime[i] == 0 if employee i has no subordinates. It is guaranteed that all the employees can be informed.

classSolution { public: intnumOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime){ vector<vector<int>> tree(n); int size = manager.size(); for (int i = 0; i < size; i++) { if (manager[i] == -1) continue; tree[manager[i]].push_back(i); } return recursive(tree, headID, informTime); } intrecursive(vector<vector<int>> &tree, int i, vector<int>& informTime){ int time = 0; for (int k : tree[i]) { time = max(time, recursive(tree, k, informTime)); } return time + informTime[i]; } };

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

Example 1:

Input: mat = [[1,0,0], [0,0,1], [1,0,0]] Output: 1 Explanation: (1,2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0. Example 2:

Input: mat = [[1,0,0], [0,1,0], [0,0,1]] Output: 3 Explanation: (0,0), (1,1) and (2,2) are special positions. Example 3:

Input: mat = [[0,0,0,1], [1,0,0,0], [0,1,1,0], [0,0,0,0]] Output: 2 Example 4:

Input: mat = [[0,0,0,0,0], [1,0,0,0,0], [0,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]] Output: 3

Constraints:

rows == mat.length cols == mat[i].length 1 <= rows, cols <= 100 mat[i][j] is 0 or 1.

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2 s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa. To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = “leEeetcode” Output: “leetcode” Explanation: In the first step, either you choose i = 1 or i = 2, both will result “leEeetcode” to be reduced to “leetcode”. Example 2:

Input: s = “abBAcC” Output: “” Explanation: We have many possible scenarios, and all lead to the same answer. For example: “abBAcC” –> “aAcC” –> “cC” –> “” “abBAcC” –> “abBA” –> “aA” –> “” Example 3:

Input: s = “s” Output: “s”

Constraints:

1 <= s.length <= 100 s contains only lower and upper case English letters.