Another Casual Coder

This problem is just laborious but requires a bit of work on Graphs (I usually build the graphs using Hashtables), traversal of graphs (in this case DFS) and string manipulation. Interesting that the standard String.CompareTo  C# does not really compare lexicographically, at least when I used it, it failed for some test cases, so I had to build my own. Long code is down below, cheers, ACC. Synonymous Sentences - LeetCode 1258. Synonymous Sentences Medium 195 75 Add to List Share You are given a list of equivalent string pairs  synonyms  where  synonyms[i] = [s i , t i ]  indicates that  s i  and  t i  are equivalent strings. You are also given a sentence  text . Return  all possible synonymous sentences  sorted lexicographically .   Example 1: Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday" Output: ["I am cheerful today but was sad yester...

1000th solved problem. Just append the character until the length is a multiple of k. Then split. Keep moving. Happy MLK Day!!! ACC Divide a String Into Groups of Size k - LeetCode 2138. Divide a String Into Groups of Size k Easy 130 8 Add to List Share A string  s  can be partitioned into groups of size  k  using the following procedure: The first group consists of the first  k  characters of the string, the second group consists of the next  k  characters of the string, and so on. Each character can be a part of  exactly one  group. For the last group, if the string  does not  have  k  characters remaining, a character  fill  is used to complete the group. Note that the partition is done so that after removing the  fill  character from the last group (if it exists) and concatenating all the groups in order, the resultant string should be  s . Given the string  s , the size of each ...

Hints that a problem requires Dynamic Programming: 1/ Starts with the problem asking for a Max or Min 2/ It usually consists of a search problem 3/ The search, for each "node", always has a dual condition: include the "node" in your search and pay a cost X, or don't include it and pay a cost Y 4/ A brute-force solution will be intractable. For example, you may end up with a complexity of 2^N, where N = 10^5... 5/ Sometimes the solution is so large that the description of the problem asks you to module the result by 10^9+7... This one is a classic one. Create an array of solutions called DP. Start with the last question, which only has one solution (itself). Work backwards and at each "node", take the max between not including it and including it. Linear space, linear time. Code is down below, cheers, ACC. Solving Questions With Brainpower - LeetCode 2140. Solving Questions With Brainpower Medium 248 1 Add to List Share You are given a  0-indexed  2D in...

I bet you probably have seen this funny symbol popping up here and there in your feeds: This is the game built by Josh Wardle "Wordle", which you can play right here:  Wordle - A daily word game (powerlanguage.co.uk) . It is an extremely simple game to play: you have 6 chances to guess the secret 5-letters word, by entering one valid 5-letter English word at a time. For each guess, the "engine" will tell you which letters you got in the right order (green), or out of order (yellow) or which ones are not present in the secret word (gray). And that's it! The implementation of such program can be done in less than 200 lines of code. Here is the approach: 1/ Find a text dictionary on the web, save it locally. The one that I have has ~62K words. Good enough to have fun, but you can have any. Moreover, any language... 2/ There will be one class called WordleGame which will control all the logic 3/ Lots of standard coding (initializing structures, reading data, selecti...

Performing a DFS can be expensive, and performing N times a DFS can be dauting, but the thing to keep in mind is the pruning. In this problem, we have a very nice condition that we perform the DFS if and only if the current course has not been processed before. Turns out that on average this will still be linear, perhaps a 2N execution time (N=10^5), but still doable. Hence the trick is to have 3 hashtables: 1/ the courses that have been taken, 2/ the list of course --> pre-requisites and 3/ the list of course --> post-requisite. Then call the DFS for each node, and check if all have been visited. Code is down below, cheers and Happy MLK Day!!! ACC Course Schedule - LeetCode 207. Course Schedule Medium 8134 317 Add to List Share There are a total of  numCourses  courses you have to take, labeled from  0  to  numCourses - 1 . You are given an array  prerequisites  where  prerequisites[i] = [a i , b i ]  indicates that you  must...

This is an interesting problem: finding all the duplicate subtrees. N=10^4, so anything N^2 is intractable. There is an interesting idea: 1/ Perform a post-order DFS (remember: post-order means left -> right -> current node) 2/ As you're going up in the tree, attach a unique hash to the node based on the structure of the subtree. Now this is the part that takes a while to figure out. What I did that work for me is a simple calculation:         BigInteger hash = (node.val + 207) * (left + 2007) * (right + 20007); The reason that I add a number greater than 200 is to avoid negative numbers (the range of the values are -200 to 200) 3/ Notice that this way two identical subtrees will have the same hash. If you find it, make sure to flag it to be added later on to the return value. That's it. Took me several attempts, but in the end it worked. Code is down below, cheers, ACC. Find Duplicate Subtrees - LeetCode 652. Find Duplicate Subtrees Medium 2787 276 Add to...

Same idea here as the other sliding window problems, except that despite the window being the size "k", we still need to keep track of the 26 letters, making the overall time complexity not O(kn), but rather O(26n), with constant space. Code is down below, cheers, ACC. Find K-Length Substrings With No Repeated Characters - LeetCode 1100. Find K-Length Substrings With No Repeated Characters Medium 327 7 Add to List Share Given a string  s  and an integer  k , return  the number of substrings in  s  of length  k  with no repeated characters .   Example 1: Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'. Example 2: Input: s = "home", k = 5 Output: 0 Explanation: Notice k can be larger than the length of s. In this case, it is not possible to find any substring.   Constraints: 1 <= s.length <= 10 4 s  consist...