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'.
Far manager network plugin 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.
0 kommentar(er)
