#FREEMIND 7 FREEPLANE SERIES#

For the two columns in each string, you set a 1 for characters with matching counts and a zero for characters with non-matching counts. And of course, 'a' itself is also valid.Īnd what was our very first optimization? A bitset - an 18-bit value the represents valid characters.

This gives us a set of all other characters that are valid when used with 'a'. For any one character that we care about (for example, the 'a'), we're looking for only the positions in both strings where its count matches, and then we're comparing these two columns to see what other values match. Here's where things get interesting, and where our character frequency counts really kick in.įirst, observe what we're actually doing on those marked columns. Here, all columns are matching except those marked with #.Īll right so you can see how this works, but you may wondering about the runtime, because those examples above seem to be doing even more scanning than you were doing before! Let's start by thinking about this in terms of a technique known as memoization where you can leverage precomputed or partially-computed information and get a whole lot out of it. For any character where that is not true, it cannot possibly be compatible with character x. Well, you extend the above premise by recognizing that for any position of character x in string 1 and some position of that character in string 2 that would be a valid match ( i.e the same number of character x appears in both strings up to their respective positions), then the total count of any other character up to those positions must also be equal. Of course, that won't help for a real stress-test which will guarantee that all possible letters have a frequency matched in both strings. In this way, you can prune the search space if such a character were to appear in the query, and you can test for this in constant time. You can count all character frequencies in both strings with a histogram which can be done in O(N) time. The next potential speedup is to recognize that any character which does not appear exactly the same number of times in both strings will instantly be a failed match. The test for membership is then basically the cost of an array lookup (and you can save operations by not doing the subtraction - instead just make the array larger and index directly by character.

Alternatively, you can have an 18-value array and index it by character ( c - 'a' would give a value between 0 and 17).The set of allowed characters is now a mask with these bits ORed together and you can test membership of a character with a bitwise-AND Represent every letter as a single bit - now every character is an 18-bit value with only one bit set.The first obvious speedup is to ensure your set membership test is O(1). However, I was told that there was a way to solve this faster in O(N). Each query takes O(N) time to process, and there are N queries, for a total of O(N^2) time. Otherwise, the s1 and s2 are equal when restricted only to letters in the query. If at some point, the characters don't match, then the strings are not equal. I was able to solve this in O(N^2) time by doing the following: For each query, I checked if s1 and s2 would be equal by iterating through both strings, one character at a time, skipping the characters that do not lie within the subset of allowed characters, and checking to see if the 'allowed' characters from both s1 and s2 match. These don't match, so the query would return false. s1 and s2 can contain up to 10^5 characters, and there are up to 10^5 queries.įor instance, if s1 is 'aabcd' and s2 is 'caabd', and you are asked to process a query with the subset 'ac', then s1 becomes 'aac' while s2 becomes 'caa'. For each query, determine whether s1 and s2, when restricted only to the letters in the query, are equal. Each query provides a subset of lowercase English letters from 'a' through 'r'.

#FREEMIND 7 FREEPLANE SERIES#

You are given two strings, s1 and s2, comprised entirely of lowercase letters 'a' through 'r', and need to process a series of queries.

Freemind 7 freeplane