Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
This comment is hidden because it contains spoiler information about the solution
Here's a great solution at O(n*m) and reduces worst case by length checking: https://www.codewars.com/kata/reviews/554cfa93085cd8af26000118/groups/567c60846776c473a000001f
Could you explain how histograms can make this O(n)? Isn't worst case always O(n*m) because you may have to check each character of each word?
I'm unfirmiliar with how histograms could even be applied here.
This is more of a DP approach than memoization, which the author particular asked for in the prompt.
If doing DP, there is no need for the list data structure. You can just keep 2 variables for n-1 and n-2. This reduces Space complexity to O(1)
This comment is hidden because it contains spoiler information about the solution
In addition, sorting takes nlogn time, where n is the number of characters. First, you can escape right away if the number of characters in item is not equal to the number of characters in word. Second, checking with histogram rather than sorting significantly improves run time, making it O(n).