A problem at which I stared for an hour

Problem: [LC2127 - Maximum Employees to Be Invited to a Meeting](https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/) A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees. The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself. Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.  Example: ##Input: favorite = [2,2,1,2] ##Output: 3 ## Explanation: The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table. All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously. Note that the company can also invite employees 1, 2, and 3, and give them their desired seats. The maximum number of employees that can be invited to the meeting is 3. ## Solution If an employee A has a favourite person, let's say employee B, and vice versa. Then we can put them together. Then we can put an employee, let's say C, whose favourite person is A on the left hand side of A. Then put an employee, let's say D, whose favourite person is C next to C. If we do the same thing for employee B, then we can have two ways to extend. Therefore, we can first look for the interdependent nodes, in this case, A & B. ``` if (a[a[i]] == i) { // TODO: calculate the left chain and the right chain } ``` Starting from node A and node B, we perform dfs to calculate the maximum nodes of the left chain and the right chain. Then we could invite $left + right + 2$ people. ``` function<int(int)> dfs = [&](int u) { if (depth[u] != -1) return depth[u]; int res = 0; for (int x : inv[u]) res = max(res, dfs(x)); return depth[u] = res + 1; }; ``` However, it would fail for the input [1,2,0] because it will output $0$ instead of $3$. In this case, we need to take care of the cyclic dependency. We need to run another dfs function for each node and check if there is a cyclic dependency. If the visited node is the entry node, then we know there is a cycle here. Then we could invite them also. ``` function<tuple<int, int, int>(int)> dfs2 = [&](int u)->tuple<int, int, int> { if (depth[u] != -1) { return { u, depth[u], 0 }; } depth[u] = 0; auto [entry, d, isCyclic] = dfs2(a[u]); if (isCyclic) { return { entry, d, 1 }; } depth[u] = d + 1; return { entry, depth[u], u == entry }; }; ``` The final answer is simple the maximum number of the result of case 1 and case 2. Here's the full solution. ``` class Solution { public: int maximumInvitations(vector<int>& a) { int n = a.size(); vector<int> depth(n, -1); vector<vector<int>> inv(n); for (int i = 0 ; i < n; i++) inv[a[i]].push_back(i); // check interdependent nodes + longest left & right chain function<int(int)> dfs = [&](int u) { if (depth[u] != -1) return depth[u]; int res = 0; for (int x : inv[u]) res = max(res, dfs(x)); return depth[u] = res + 1; }; int mx1 = 0, mx2 = 0; for (int i = 0; i < n; i++) { if (depth[i] != -1) continue; if (a[a[i]] == i) { depth[i] = depth[a[i]] = 0; int left = 0, right = 0; for (int x : inv[i]) if (x != a[i]) left = max(left, dfs(x)); for (int x : inv[a[i]]) if (x != a[i]) right = max(right, dfs(x)); mx1 += left + right + 2; } } // check cyclic dependency function<tuple<int, int, int>(int)> dfs2 = [&](int u)->tuple<int, int, int> { if (depth[u] != -1) { return { u, depth[u], 0 }; } depth[u] = 0; auto [entry, d, isCyclic] = dfs2(a[u]); if (isCyclic) { return { entry, d, 1 }; } depth[u] = d + 1; return { entry, depth[u], u == entry }; }; for (int i = 0; i < n; i++) { if (depth[i] != -1) continue; auto [entry, d, isCyclic] = dfs2(i); if (isCyclic) { mx2 = max(mx2, d); } } return max(mx1, mx2); } }; ```

LeetCode - Weekly Contest 273 Editorial

## [Q1: A Number After a Double Reversal](https://leetcode.com/problems/a-number-after-a-double-reversal/) If you just do what it says, here's the code. ```cpp class Solution { public: bool isSameAfterReversals(int num) { if (num == 0) return 1; string s = to_string(num); int n = s.size(), j = 0; while (s[n - 1 - j] == '0') j++; string t = s.substr(0, n - j); return s == t; } }; ``` However, a better way to solve this is to check if there is any trailing zero. No matter how many zeros at the end, after removing them all, it won't be same if you reverse it. The only exceptional case is $num = 0$. ``` class Solution { public: bool isSameAfterReversals(int num) { return num == 0 || num % 10; } }; ``` ## [Q2: Execution of All Suffix Instructions Staying in a Grid](https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/) We can just simulate the whole process. For each $i-th$ instruction, we have max $ s.size() - i $ steps assuming $ i $ starts from $ 0 $. We keep updating the position $(x, y)$ and check if it is out of bound. If not, keep inceasing $cnt$ by 1. If there is no further move we can make, we can break the loop and push the result $cnt$ to $ans$. ``` class Solution { public: vector executeInstructions(int n, vector& startPos, string s) { int m = s.size(); vector ans; for (int i = 0; i < m; i++) { int x = startPos[0]; int y = startPos[1]; int cnt = 0; for (int j = i; j < m; j++) { if (s[j] == 'L') y--; if (s[j] == 'R') y++; if (s[j] == 'U') x--; if (s[j] == 'D') x++; if (0 <= x && x < n && 0 <= y && y < n) cnt++; else break; } ans.push_back(cnt); } return ans; } }; ``` However, the above brute-force solution gives $O(m^2)$ complexity. It works because $m$ is just limited to $1000$. There's a $O(m)$ solution. ``` class Solution { public: vector executeInstructions(int n, vector& startPos, string s) { int m = s.size(), h = m + n, v = m + n; vector hor((m + n) * 2, m), ver((m + n) * 2, m), ans(m); for (int i = m - 1; i >= 0; i--) { hor[h] = ver[v] = i; if (s[i] == 'L') h++; if (s[i] == 'R') h--; if (s[i] == 'U') v++; if (s[i] == 'D') v--; ans[i] = min({ m, hor[h - startPos[1] - 1], hor[h - startPos[1] + n], ver[v - startPos[0] - 1], ver[v + startPos[0] * -1 + n] }) - i; } return ans; } }; ``` ## [Intervals Between Identical Elements](intervals-between-identical-elements) First we need to know the indices for each number. We can easily construct it using ``unordered_map<int, vector<int>>``. Then it comes to the math part. Our goal is to calculate the absolute difference for numbers smaller than and greater than or equal to $k$ in linear time. Let's say the list is [1, 3, 5, 7, 9] and let $k$ be $7$. The absolute difference for numbers smaller than or equal to $7$ is $(7 - 1) + (7 - 3) + (7 - 5) - (7 - 7)$. We can arrange it to $ 7 * 4 - (1 - 3 - 5 - 7)$ which is same as $k * (i + 1) - pre[i + 1]$. Similarly, let $k$ be $3$ and we want to find out the absolute difference for numbers greater than or equal to $3$. $(3 - 3) + (3 - 5) + (3 - 7) + (3 - 9)$. We can arrange it to $3 * 4 - (3 + 5 + 7 + 9)$, which is same as $(pre[n] - pre[i]) - k * (n - i)$. Therefore, $ans[k]$ would be the sum of the left part and the right part. Prefix sum can be calculated as ``` for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + v[i]; } ``` ``` class Solution { public: vector<long long> getDistances(vector& arr) { unordered_map<int, vector<int>> m; vector<long long> ans(arr.size()); int n = arr.size(); for (int i = 0; i < n; i++) { m[arr[i]].push_back(i); } for (auto x : m) { vector v = x.second; int n = v.size(); vector<long long> pre(n + 1); for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + v[i]; } for (int i = 0; i < n; i++) { long long k = v[i]; ans[k] = (k * (i + 1) - pre[i + 1]) + (pre[n] - pre[i] - k * (n - i)); } } return ans; } }; ``` ## [Recover the Original Array](https://leetcode.com/problems/recover-the-original-array/) In short, we just need to try all possible $k$. If we sort $nums$, the smallest elelment must be in the lower array. It is easy to see $k$ can be $(nums[i] - nums[0]) / 2$. We try each $k$ to see if we can match all the pairs. If the size of lower array is same as that of higher array, then the ans would be $ans[j] = (l[j] + r[j]) / 2$. ``` class Solution { public: vector recoverArray(vector& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { unordered_map<int, int> m; int d = nums[i] - nums.front(); if (d == 0 || d & 1) { continue; } vector l, r; for (int j = 0; j < n; j++) { if (m.count(nums[j] - d)) { r.push_back(nums[j]); if (--m[nums[j] - d] == 0) { m.erase(nums[j] - d); } } else { l.push_back(nums[j]); m[nums[j]]++; } } if (l.size() == r.size()) { vector ans; for (int j = 0; j < n / 2; j++) { ans.push_back((l[j] + r[j]) / 2); } return ans; } } return {}; } }; ```

The Easiest LeetCode Contest in 2021

This LeetCode contest is sponsored by Amazon Pay. Check out [Weekly Contest 272](https://leetcode.com/contest/weekly-contest-272) for the questions. ## Q1 - 2108. Find First Palindromic String in the Array Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "". A string is palindromic if it reads the same forward and backward. ### Example 1: Input: words = ["abc","car","ada","racecar","cool"] Output: "ada" Explanation: The first string that is palindromic is "ada". Note that "racecar" is also palindromic, but it is not the first. ### Example 2: Input: words = ["notapalindrome","racecar"] Output: "racecar" Explanation: The first and only string that is palindromic is "racecar". ### Example 3: Input: words = ["def","ghi"] Output: "" Explanation: There are no palindromic strings, so the empty string is returned. ## Solution There are several ways to check if $s$ is a palindrome. ### Long and Efficient ```cpp bool isPalindrome(const string& s) { for (int i = 0; i < s.size() / 2; i++) { if (s[i] != s[s.size() - i - 1]) return false; } return true; } ``` ### Shorter but not efficient ```cpp bool isPalindrome(const string& s) { string t = s; reverse(t.begin(), t.end()); return s == t; } ``` ### Shortest but not efficient ```cpp bool isPalindrome(const string& s) { return s == string(s.rbegin(), s.rend()); } ``` ### Shortest but efficient ```cpp bool isPalindrome(const string &s) { return equal(s.begin(), s.begin() + s.size() / 2, s.rbegin()); } ``` We just need to iterate each string and check if the target $s$ is a palindrome, return the string if so. ``` class Solution { public: bool isPalindrome(const string& s) { return equal(s.begin(), s.begin() + s.size() / 2, s.rbegin()); } string firstPalindrome(vector& words) { for (auto s : words) { if (isPalindrome(s)) { return s; } } return ""; } }; ``` ## Q2 - 2109. Adding Spaces to a String You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index. For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee". Return the modified string after the spaces have been added. ### Example 1: Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15] Output: "Leetcode Helps Me Learn" Explanation: The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn". We then place spaces before those characters. ### Example 2: Input: s = "icodeinpython", spaces = [1,5,7,9] Output: "i code in py thon" Explanation: The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython". We then place spaces before those characters. ### Example 3: Input: s = "spacing", spaces = [0,1,2,3,4,5,6] Output: " s p a c i n g" Explanation: We are also able to place spaces before the first character of the string. ## Solution Two-pointer. i-th pointer is for string $s$ and j-th pointer is for spaces vector. Iterate string $s$, if $i$ matches $spaces[j]$, then add a space and increase $j$ by 1. ``` class Solution { public: string addSpaces(string s, vector& spaces) { string ans; int j = 0, m = spaces.size(); for (int i = 0; i < s.size(); i++) { if (j < m && i == spaces[j]) ans += " ", j++; ans += s[i]; } return ans; } }; ``` ## Q3 - 2110. Number of Smooth Descent Periods of a Stock You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the ith day. A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule. Return the number of smooth descent periods. ### Example 1: Input: prices = [3,2,1,4] Output: 7 Explanation: There are 7 smooth descent periods: [3], [2], [1], [4], [3,2], [2,1], and [3,2,1] Note that a period with one day is a smooth descent period by the definition. ### Example 2: Input: prices = [8,6,7,7] Output: 4 Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7] Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1. ### Example 3: Input: prices = [1] Output: 1 Explanation: There is 1 smooth descent period: [1] ## Solution The first observation is each number is a smooth descent period. The final answer is at least $ n $ which is the size of the given vector. Therefore, the initial value for $dp[i]$ is $1$. The second observation is that we can add $dp[i - 1]$ to $dp[i]$ if $prices[i - 1] - prices[i] = 1$ starting from $i = 1$. ``` class Solution { public: long long getDescentPeriods(vector& prices) { int n = prices.size(); long long ans = 0; vector dp(n, 1); for (int i = 0; i < n; i++) { if (i > 0 && prices[i - 1] - prices[i] == 1) { dp[i] += dp[i - 1]; } ans += dp[i]; } return ans; } }; ``` ## Q4 - 2111. Minimum Operations to Make the Array K-Increasing You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k. The array arr is called K-increasing if arr[i-k] <= arr[i] holds for every index i, where k <= i <= n-1. For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because: arr[0] <= arr[2] (4 <= 5) arr[1] <= arr[3] (1 <= 2) arr[2] <= arr[4] (5 <= 6) arr[3] <= arr[5] (2 <= 2) However, the same arr is not K-increasing for k = 1 (because arr[0] > arr[1]) or k = 3 (because arr[0] > arr[3]). In one operation, you can choose an index i and change arr[i] into any positive integer. Return the minimum number of operations required to make the array K-increasing for the given k. ### Example 1: Input: arr = [5,4,3,2,1], k = 1 Output: 4 Explanation: For k = 1, the resultant array has to be non-decreasing. Some of the K-increasing arrays that can be formed are [5,6,7,8,9], [1,1,1,1,1], [2,2,3,4,4]. All of them require 4 operations. It is suboptimal to change the array to, for example, [6,7,8,9,10] because it would take 5 operations. It can be shown that we cannot make the array K-increasing in less than 4 operations. ### Example 2: Input: arr = [4,1,5,2,6,2], k = 2 Output: 0 Explanation: This is the same example as the one in the problem description. Here, for every index i where 2 <= i <= 5, arr[i-2] <= arr[i]. Since the given array is already K-increasing, we do not need to perform any operations. ### Example 3: Input: arr = [4,1,5,2,6,2], k = 3 Output: 2 Explanation: Indices 3 and 5 are the only ones not satisfying arr[i-3] <= arr[i] for 3 <= i <= 5. One of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5. The array will now be [4,1,5,4,6,5]. Note that there can be other ways to make the array K-increasing, but none of them require less than 2 operations. ## Solution We can break input vector into $k$ groups $a_i, a_{i + k}, a_{i + 2 * k}, ...$ for each $ i < k$. Calculate the LIS (Longest Increasing Subsequence) on each group and compare the length with the target size. We need to perform $a.size() - lengthOfLIS(a)$ operations to make it K-increasing. ``` class Solution { public: int lengthOfLIS(vector& nums) { int n = (int) nums.size(); vector lis; for(int i = 0; i < n; i++) { auto it = upper_bound(lis.begin(), lis.end(), nums[i]); if(it == lis.end()) lis.push_back(nums[i]); else *it = nums[i]; } return (int) lis.size(); } int kIncreasing(vector& arr, int k) { int ans = 0, n = arr.size(); for (int i = 0; i < k; i++) { vector a; for (int j = i; j < n; j += k) { a.push_back(arr[j]); } ans += a.size() - lengthOfLIS(a); } return ans; } }; ```

Eulerian path / Hierholzer's Algorithm

 ### Eulerian Trail / Path It is a trail in a finite graph that every edge will be visited exactly once. ### Eulerian Cycle / Circuit / Tour It is an Eulerian trail that starts and ends on the same vertex. ### Euler's Theorem A connected graph has an Euler cycle if and only if every vertex has even degree. ### Properties - An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component. - An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component. - An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component. - A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component. - A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph. ## Problem #1: LC2097 - Valid Arrangement of Pairs (Hard) You are given a 0-indexed 2D integer array pairs where $ pairs[i] = [start_i, end_i] $. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have $end_i - 1 $ == $start_i$. Return any valid arrangement of pairs. Note: The inputs will be generated such that there exists a valid arrangement of pairs. ``` Input: pairs = [[5,1],[4,5],[11,9],[9,4]] Output: [[11,9],[9,4],[4,5],[5,1]] ``` ## Idea: Using Hierholzer's Alogorithm We can construct Eulerian trails and circuits using Fleury's algorithm or Hierholzer's algorithm. However, the latter one is more efficient than Fleury's algorithm. Here's the general idea. - Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph. - As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour. - Since we assume the original graph is connected, repeating the previous step will exhaust all edges of the graph. ## Solution: - Search the starting point of an Eulerian Path, i.e. $ out[i] == in[i] + 1 $. If we got $ out[i] == in[i] $ for all $ i $, then we can start at any arbitrary node (the first node is chosen in this solution). - Perform ``euler``, a post-order dfs function` on the graph. Walk through an edge and erase the visited edge. - Push the ``src`` and ``nxt`` to ``paths``. ``` void euler(unordered_map<int, vector<int>>& g, int src, vector<vector<int>>& paths) { while(!g[src].empty()) { int nxt = g[src].back(); g[src].pop_back(); euler(g, nxt, paths); paths.push_back({src, nxt}); } } vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { vector<vector<int>> ans; int n = (int) pairs.size(); unordered_map<<int, vector<int>> g; unordered_map<int, int> in, out; for(auto x : pairs) { g[x[0]].push_back(x[1]); in[x[1]]++; out[x[0]]++; } int src = -1; for(auto x : g) { int i = x.first; if(out[i] - in[i] == 1) { src = i; break; } } if(src == -1) { src = g.begin()->first; } euler(g, src, ans); reverse(ans.begin(), ans.end()); return ans; } ``` ## Problem #2: LC332 - Reconstruct Itinerary (Hard) You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"]. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.  ``` Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"] ``` ## Idea: Using Hierholzer's Alogorithm Similar to LC2097, in this problem, we don't need to search for the starting point as the itinerary must begin with ``JFK``. The black edges represent unvisited edge, green edges are visited edges, and brown edges are backtrack edges.  ## Solution: - Sort tickets based on the destination so that it could get the smaller edge first. - Perform ``euler``, a post-order dfs function` on the graph. Walk through an edge and erase the visited edge. - Push node to ``ans`` when all its edges are processed. ``` void euler(unordered_map<string, queue<string>>& g, string src, vector<string>& ans) { while(!g[src].empty()) { string nxt = g[src].front(); g[src].pop(); euler(g, nxt, ans); } ans.push_back(src); } vector<string> findItinerary(vector<vector<string>>& tickets) { vector<string> ans; sort(tickets.begin(), tickets.end(), [&](const vector& x, const vector& y) { return x[1] < y[1]; }); unordered_map<string, queue<string>> g; for(auto x : tickets) { g[x[0]].push(x[1]); } string src = "JFK"; euler(g, src, ans); reverse(ans.begin(), ans.end()); return ans; } ``` ## Problem #3: CSES1691 - Mail Delivery Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once. Input The first input line has two integers n and m: the number of crossings and streets. The crossings are numbered 1,2,…,n, and the post office is located at crossing 1. After that, there are m lines describing the streets. Each line has two integers a and b: there is a street between crossings a and b. All streets are two-way streets. Every street is between two different crossings, and there is at most one street between two crossings. Output Print all the crossings on the route in the order you will visit them. You can print any valid solution. If there are no solutions, print "IMPOSSIBLE". ## Solution: ``` vector ans; vector> g; const int mxN = 1e6 + 5; void euler(int src) { while(g[src].size()) { int nxt = *g[src].begin(); g[nxt].erase(src); g[src].erase(nxt); euler(nxt); } ans.push_back(src); } void solve() { int n, m; cin >> n >> m; g.resize(mxN); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; --a, --b; g[a].insert(b); g[b].insert(a); } for(int i = 0; i < n; i++) { if(g[i].size() & 1) { cout << "IMPOSSIBLE" << endl; return; } } euler(0); if(ans.size() != m + 1) { cout << "IMPOSSIBLE" << endl; return; } reverse(ans.begin(), ans.end()); for(int i = 0; i < m + 1; i++) { cout << ans[i] + 1 << " \n"[i == m]; } } ```

De Bruijn Sequence

De Bruijn Sequence is a binary sequence of order $ n $ of bits $b_i \in {0, 1} $ where $ b = {b_i, ..., b_{2^n}}$ such that every string of length $ n $ ${a_1, ..., a_n} \in $ {0, 1} $ ^ n $ occurs exactly once consecutively in $b$. To generate a De Bruijn Sequence, we need to get the Euler circuit for the graph for all $ n - 1 $ possible stringds. For example, given $ n = 4 $ & $ k = 2 $,  We would have a sequence of length $2 ^ 4 = 16$ using Eulerian $k$-D de Bruijn graph cycle where $k = n - 1$ which is 3 in this case. Each edge will be traversed exactly once to use each of the 16 4-digit sequences exactly once. The Eulerian path is $$ 000, 000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000. $$ The de Bruijn sequence is $$ 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 $$ For output sequences of length $ k = 4 $, we got ``` {0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ... ``` To find Euler circuit, we can use Hierholzer’s algorithm to get it in linear time. If we randomly traverse the graph without repeating edges, it will eventually end up on the same vertex but the path may not include all the edges. Therefore, we have to remove those visited edges from the graph, which will split into several components. All the components contain Euler Circuit. ## [Cracking the Safe (Hard)](https://leetcode.com/problems/cracking-the-safe/) There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1]. The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit. For example, the correct password is "345" and you enter in "012345": After typing 0, the most recent 3 digits is "0", which is incorrect. After typing 1, the most recent 3 digits is "01", which is incorrect. After typing 2, the most recent 3 digits is "012", which is incorrect. After typing 3, the most recent 3 digits is "123", which is incorrect. After typing 4, the most recent 3 digits is "234", which is incorrect. After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks. What is the string of minimum length that will unlock the safe at some point of entering it? For example, $ n = 2, k = 2 $, one of the possible answers is $01100$ because we can type $01$ from the $1st$ digit, $11$ from the $2nd$ digit, $10$ from the $3rd$ digit, and $00$ from the $4th$ digit. ## Solution ```cpp class Solution { public: string ans; vector> vis; int n, k, v; void dfs(int u) { for(int i = 0; i < k; i++) { if(!vis[u][i]) { vis[u][i] = 1; dfs((u * k + i) % v); ans += '0' + i; } } } string crackSafe(int n, int k) { if(k == 1) return string(n, '0'); this->n = n, this->k = k; v = pow(k, n - 1); // vis[k ^ (n - 1)][k] vis.resize(v, vector(k)); dfs(0); return ans + ans.substr(0, n - 1); } }; ```

LeetCode - Paint House

These problems are basically same except the constraints. In the first question, ``k`` is always 3. If we solve the second problem, then we can also solve the first problem. Therefore, let's think about the case when ``k`` is not fixed. ## Paint House (Medium) [Paint House (Medium)](https://leetcode.com/problems/paint-house/) There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs. For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Return the minimum cost to paint all houses. ## Paint House II (Hard) [Paint House II (Hard)](https://leetcode.com/problems/paint-hous-ii/) There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by an n x k cost matrix costs. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Return the minimum cost to paint all houses. ## Solution 1 : Dynamic Programming Supposing we got 5 houses and 6 colors (red, green, blue, yellow, purple, orange). Starting from the second, we can only choose the different color from the previous row. For example, if costs[1][0] is selected, then the only possible color to be chosen from the previous row must be from column 1 to column 5 and pick the minimum costs[0][j] where $j \neq 0$ in this example.  Therefore, we iterate each color in the current row and compare it from the previous row to find the minimum cost. The following solution gives $O(n * k ^ 2)$ time complexity and $O(k)$ space complexity. ```python def minCostII(self, costs: List[List[int]]) -> int: n = len(costs) k = len(costs[0]) prev_row = costs[0] for house in range(1, n): cur_row = [0] * k for cur_color in range(k): prev_best = math.inf for prev_color in range(k): if cur_color == prev_color: continue prev_best = min(prev_best, prev_row[prev_color]) cur_row[cur_color] += prev_best + costs[house][cur_color] prev_row = cur_row return min(prev_row) ``` which can be written in a cleaner way. ```python def minCostII(self, costs: List[List[int]]) -> int: k = len(costs[0]) prev_row = [0] * k for cur_row in costs: prev_row = [cur_row[i] + min(prev_row[:i] + prev_row[i + 1:]) for i in range(k)] return min(prev_row) ``` ## Solution 2: Markov Chain If ``n`` and ``k`` are set to $500$, then Solution 1 will exceed time limit. Here's another solution using the idea of Markov Chain. Given that ``k`` states (colors) and ``n`` stages, we can update the matrix to find out the optimal value for each state at the current stage. The idea is to find out the first and the second minimum cost for each stage. For the next stage, we can update each cost by adding either the first minimum cost or the second one. The reason we need two minimum cost is that we cannot paint the same color. If the index of the first minimum cost from the previous stage is ``i`` and we have to use the second minimum cost for the current stage, and vice versa. ```python class Solution: def solve(self, matrix): n = len(matrix) k = len(matrix[0]) for house in range(1, n): first_mi_color = second_mi_color = None # find first & second min color for color in range(k): cost = matrix[house - 1][color] if first_mi_color is None or cost < matrix[house - 1][first_mi_color]: second_mi_color = first_mi_color first_mi_color = color elif second_mi_color is None or cost < matrix[house - 1][second_mi_color]: second_mi_color = color # update matrix for the current row for color in range(k): if color == first_mi_color: matrix[house][color] += matrix[house - 1][second_mi_color] else: matrix[house][color] += matrix[house - 1][first_mi_color] return min(matrix[-1]) ``` Here's the shorter version. ```python class Solution: def minCostII(self, costs: List[List[int]]) -> int: n, k = len(costs), len(costs[0]) for house in range(1, n): first_mi_cost = min(costs[house - 1]) idx = costs[house - 1].index(first_mi_cost) second_mi_cost = min(costs[house - 1][:idx] + costs[house - 1][idx + 1:]) for color in range(k): if color == idx: costs[house][color] += second_mi_cost else: costs[house][color] += first_mi_cost return min(costs[-1]) ```

LeetCode Weekly Contest 256 - Editorials

Here's the editorials for [LeetCode Weekly Contest 256](https://leetcode.com/contest/weekly-contest-256/) ## [Minimum Difference Between Highest and Lowest of K Scores (3 points)](https://leetcode.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores/) The question can be rephrased as finding the minimum difference between the lowest and highest element of window of size ``k``. Therefore, we can first sort the array and check all the differences for each window. ```cpp class Solution { public: int minimumDifference(vector& nums, int k) { sort(nums.begin(), nums.end()); int ans = INT_MAX, n = nums.size(); for(int i = 0; i < n - k + 1; i++) { ans = min(ans, nums[i + k - 1] - nums[i]); } return ans; } }; ``` ## [Find the Kth Largest Integer in the Array (4 points)](https://leetcode.com/problems/find-the-kth-largest-integer-in-the-array/) If the input is integer, then we can sort the array and the answer would be $ nums[n - 1 - (k - 1)] $. However, this question gives an array of strings. Therefore, we just need to convert it to an array of integers first and perform the abovementioned logic. ```cpp class Solution { public: string kthLargestNumber(vector& nums, int k) { int n = nums.size(); sort(nums.begin(), nums.end(), [](string& s, string& t){ if(s.size() < t.size()) return true; if(t.size() < s.size()) return false; return s < t; }); return nums[n - k]; } }; ``` ## [Minimum Number of Work Sessions to Finish the Tasks (6 points)](https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/) Same question as [Elevator Rides](https://cses.fi/problemset/result/2762549/). Greedy approach won't work here. Here's the Bitmask DP approach. Let's define $ dp[i][j] $ where $i$ is the mask, $j$ is the minimum time for finishing the current tasks, and $dp[i][j]$ stores the minimum number of work sessions needed to finish all the tasks. We can run a dfs function to calculate each mask, if a task is not picked, we can set it as a new mask and check if adding this task would exceed sessionTime or not. If so, that means we need to create a new session and we can perform the next mask. Otherwise, we can just add this task to the current work session and try the next mask. ```cpp class Solution { public: int dp[1 << 14][20]; vector t; int time; int dfs(int m, int k) { int n = t.size(); if(m == (1 << n) - 1) return 1; if(dp[m][k] != -1) return dp[m][k]; int best = INT_MAX, new_mask; for(int i = 0; i < n; i++) { if(!(m & (1 << i))) { int new_mask = m | (1 << i); if(k + t[i] <= time) { best = min(best, dfs(new_mask, k + t[i])); } else { best = min(best, 1 + dfs(new_mask, t[i])); } } } return dp[m][k] = best; } int minSessions(vector& tasks, int sessionTime) { memset(dp, -1, sizeof(dp)); t = tasks, time = sessionTime; return dfs(0, 0); } }; ``` However, this method is not that efficient. Let's define $ dp[i] $ where $i$ is the mask and $dp[i]$ stores a pair of integers, with the first element as the minimum number of sessions and the second element as minimum time of the last session. After all tasks have been picked, that would be all 1s. Therefore, the answer is $dp[(1 << n) - 1]$. For each mask, we try to find the best pair, the logic is similar to the first approach. ```cpp class Solution { public: int minSessions(vector& tasks, int sessionTime) { int n = tasks.size(), INF = 1e9; // {min number of session, min time of last session} vector<pair<int, int>> dp(1 << n, {INF, INF}); dp[0].first = 0; for(int mask = 1; mask < (1 << n); mask++) { pair<int, int> best = {INF, INF}; for(int i = 0; i < n; i++) { if(mask & (1 << i)) { pair<int, int> cur = dp[mask ^ (1 << i)]; if(cur.second + tasks[i] > sessionTime) { cur = {cur.first + 1, tasks[i]}; } else { cur.second += tasks[i]; } best = min(best, cur); } } dp[mask] = best; } return dp[(1 << n) - 1].first; } }; ``` ## [Number of Unique Good Subsequences (7 points)](https://leetcode.com/problems/number-of-unique-good-subsequences/) The transition formula can be easily obtained by listing out some examples. We just need to count the number of subsequence that ends with 0 and 1, says $dp[0]$ and $dp[1]$. If $s[i] = 0$, we can append this $0$ to all existing subsequences, i.e. $dp[0] = dp[0] + dp[1]$. Simiarly, we can append $1$ to all the subsequences so that we got $dp[1] = dp[0] + dp[1] + 1$. We add $1$ here because $1$ is also a valid subsequence. $0$ is also a valid subsequence, but it will fail with something like $01$ or $00$. Therefore, we can simply add one at the end instead. The final answer is $dp[0] + dp[1]$ + $zero$ where $zero$ is either $1$ if there is at least one zero in the string, or $0$ otherwise. ```cpp class Solution { public: int numberOfUniqueGoodSubsequences(string binary) { int M = 1e9 + 7, dp[2] = {0, 0}; for(char& c: binary) dp[c - '0'] = (dp[0] + dp[1] + c - '0') % M; return (dp[0] + dp[1] + (binary.find("0") != string::npos)) % M; } }; ```

LeetCode - 1062. Longest Repeating Substring

# Problem Statement Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists. # Approach 1 : Dynamic Programming The problem can be rephased as finding out the length of the longest common substring and we don't need to care about the occurrence of repeating substrings. We can solve it using dynamic programming. Let's define $ dp[i][j] $ as the maximum length of longest common subarray ending with S[i] and S[j]. The base case is when $ i $ or $ j $ is 0, then dp[i][j] must be 0. Else we can start from $ i = 1 .. n $ and $ j = 1 .. m $. If two characters are equal, we can set the current dp[i][j] to the previous state dp[i - 1][j - 1] plus one. Since we are looking for the maximum value here so for each update we check if the current state is greater than the current answer. The time complexity for this solution is $ O(n ^ 2) $. ```cpp int longestRepeatingSubstring(string S) { int n = S.size(); vector> dp(n + 1, vector(n + 1)); int ans = 0; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { if(S[i - 1] == S[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; ans = max(ans, dp[i][j]); } } } return ans; } ``` # Approach 2 : Binary Search + Sliding Windows + Set Another approach is to use binary search to find out the window size $ L $ and put each string within this window to a set. If the string is already seen, that means this substring is repeating. The average time complexity would be $ O(n log n)$. ```cpp int ok(string S, int m, int n) { unordered_set s; string tmp; for(int i = 0; i < n - m + 1; i++) { tmp = S.substr(i, m); if(s.count(tmp) > 0) return i; s.insert(tmp); } return -1; } int longestRepeatingSubstring(string S) { int n = S.size(); int l = 1, r = n, m; while(l <= r) { m = l + (r - l) / 2; if(ok(S, m, n) != -1) l = m + 1; else r = m - 1; } return l - 1; } ``` # Approach 3 : Binary Search + Sliding Windows + Set of Hash values The previous approach can be further fine-tuned as the length of string can go up to 1500. We can reduce the memory consumption by storing the hash value of the string instead of the string itself. ```cpp int ok(string S, int m, int n) { unordered_set s; string tmp; for(int i = 0; i < n - m + 1; i++) { tmp = compute_hash(S.substr(i, m)); if(s.count(tmp) > 0) return i; s.insert(tmp); } return -1; } ``` For the function ``compute_hash``, we can use a polynomial rolling hash function. Generally given the string S and the length N, the function can be defined as: $$ H(S) = S[0] + S[1] * P + S[2] * P ^ 2 + ... + S[N - 1] * P ^ {N - 1} \pmod M $$ $$ = \sum\limits_{i = 0}^{N - 1} {S[i] * P^i} \pmod M $$ In this problem, the string S consists of only lowercase English letters from 'a' - 'z'. Hence, we can make the closest prime number which is greater or equal to the input alphabet. In this case, it is 31. If it contains both uppercase and lowercase, we could use $ p = 53 $. For M, we should use a large prime number. $ 10 ^ 9 + 9 $ will be used in this problem. ```cpp string compute_hash(string const& s) { const int p = 31; const int m = 1e9 + 9; long long hash_value = 0; long long p_pow = 1; for (char c : s) { hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m; p_pow = (p_pow * p) % m; } return to_string(hash_value); } ```