Algo Advance

2246. Longest Path With Different Adjacent Characters You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1. You are also given a string s of length n, where s[i] is the character assigned to node i. Return the length of the longest path in the tree such that no pair of adjacent nodes on the path have the same character assigned to them. Constraints: n == parent.length == s.length 1 <= n <= 10^5 0 <= parent[i] <= n - 1 for all i >= 1 parent[0] == -1 parent represents a valid tree. s consists of only lowercase English letters. Analysis For this question, we need to construct a graph, or more specifically, a n-nary tree. How to construct the graph/tree? What we only know is the parent array. So we need to go through the parent array and constr...

 2192. All Ancestors of a Node in a Directed Acyclic Graph You are given a positive integer n representing the number of nodes of a Directed Acyclic Graph (DAG). The nodes are numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges, where edges[i] = [fromi, toi] denotes that there is a unidirectional edge from fromi to toi in the graph. Return a list answer, where answer[i] is the list of ancestors of the ith node, sorted in ascending order. A node u is an ancestor of another node v if u can reach v via a set of edges. Constraints: 1 <= n <= 1000 0 <= edges.length <= min(2000, n * (n - 1) / 2) edges[i].length == 2 0 <= fromi, toi <= n - 1 fromi != toi There are no duplicate edges. The graph is directed and acyclic. Analysis: This question can be solved by constructing a graph by the edges information. Since this question asks for the parents information, we can create a graph storing the direct parents notes.  After having the graph,...

Depth-first-search - medium level - question 2 2115. Find All Possible Recipes from Given Supplies You have information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The ith recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. Ingredients to a recipe may need to be created from other recipes, i.e., ingredients[i] may contain a string that is in recipes. You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them. Return a list of all the recipes that you can create. You may return the answer in any order. Note that two recipes may contain each other in their ingredients. Constraints: n == recipes.length == ingredients.length 1 <= n <= 100 1 <= ingredients[i].length, supplies.length <= 100 1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10 recipes[i...

1316. Distinct Echo Substrings Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string). Constraints: 1 <= text.length <= 2000 text has only lowercase English letters. Analysis: There are O(N^2) substring in total, and if we check each substring one by one, the time complexity for checking is O(N). So the overall time complexity is O(N^3). The longest test case may have N as 2000, so N^3 ~ 10^10, which is too large. We need to find some other ways faster. One way is to use a rolling hashing method. For a fixed length, we just scan the string from left to right once with double pointers. The first pointer is the ending of the first half; the second one is the ending of the second half. If they are the same, or give the same hash value, then we consider they are the same. To avoid repeating counting, we can use a set. See the code below, class Solution { pu...

2156. Find Substring With Given Hash Value The hash of a 0-indexed string s of length k, given integers p and m, is computed using the following function: hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m. Where val(s[i]) represents the index of s[i] in the alphabet from val('a') = 1 to val('z') = 26. You are given a string s and the integers power, modulo, k, and hashValue. Return sub, the first substring of s of length k such that hash(sub, power, modulo) == hashValue. The test cases will be generated such that an answer always exists. A substring is a contiguous non-empty sequence of characters within a string. Constraints: 1 <= k <= s.length <= 2 * 104 1 <= power, modulo <= 109 0 <= hashValue < modulo s consists of lowercase English letters only. The test cases are generated such that an answer always exists. Analysis This is question is about rolling hash. The formula is given, but we cannot use it directly. Or ...

Rolling Hash - Question List Question 1.  2156. Find Substring With Given Hash Value Question 2.  1316. Distinct Echo Substrings Upper Layer

Rolling hash is one common trick used to increase efficiency of substring comparisons by compressing (or hashing) a string into a integer. After this step, we can compare two strings directly without comparing each chars. So the efficiency can be increased from O(N) to O(1). So how to implement the rolling hash? First we need to choose a base for the expansion and a modulo to mod. The basic formula is (suppose the window is n, and the rolling direction is from left to right), HashVal = (A1*p^(n-1) + A2*p^(n-2) + ... + An-1*p^1 + An*p^0)%mod where HashVal is the hash value, Ai is the ith element, p is the base, and mod is the modulo. To avoid collision as much as we can, p and modulo usually need to be large prime numbers. One corner case is that the base order in the above formula cannot be reversed. Or to be more clear, if the rolling direction is from left to right in an array, the first element should be in the highest order of the base, or times p^(n-1), and the last element times ...