N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3] Output: 1 Explanation: We only need to swap the second (row[1]) and third (row[2]) person. Example 2:

Input: row = [3, 2, 0, 1] Output: 0 Explanation: All couples are already seated side by side. Note:

len(row) is even and in the range of [4, 60]. row is guaranteed to be a permutation of 0…len(row)-1.

bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it’s guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned. Follow up: Could you implement the functions of the class with each function works in average O(1) time?

Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

-2^31 <= val <= 2^31 - 1 At most 105 calls will be made to insert, remove, and getRandom. There will be at least one element in the data structure when getRandom is called.

classRandomizedSet { public: /** Initialize your data structure here. */ RandomizedSet() { } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ boolinsert(int val){ if (maps.count(val) > 0) returnfalse; data.push_back(val); maps[val] = data.size() - 1; returntrue; } /** Removes a value from the set. Returns true if the set contained the specified element. */ boolremove(int val){ if (maps.count(val) > 0) { int idx = maps[val]; maps.erase(val); if (idx != data.size() - 1) { data[idx] = data.back(); maps[data.back()] = idx; } data.pop_back(); returntrue; } returnfalse; } /** Get a random element from the set. */ intgetRandom(){ int size = data.size(); int idx = rand() % size; return data[idx]; } private: unordered_map<int, int> maps; //val -> pos vector<int> data; };

/** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet* obj = new RandomizedSet(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */

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.

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; }

intget_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]); }

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:

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.

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:

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:

classSolution { public: intminMoves(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; } };

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).

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

classSolution { public: intnumSteps(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; } };

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.