# Is there an efficient way to determine the number of subarrays or substrings that have a certain property?

The naive solution is to generate the set of subarrays/substrings and check each for the property, but that is very inefficient. Is there a general algorithm that offers better performance without knowing more about the data or the criteria themselves?

The substrings would be defined as contiguous subsets. So for instance, "123" would give "1", "2", "3", "12", "23" and "123". The property could be anything about the values of the subset, for instance the product of the values (when converted to ints) is equal to some value.

• It would depend on the property. The answer for the property "contains a 2" is different from the answer for "is a prime number".
– Ivan
Sep 9, 2016 at 13:56
• You need to exploit the specifics of the property you're interested in to beat the naive solution. Sep 9, 2016 at 14:58
• Could you elaborate on what kind of efficiency or performance you are looking for? Are you looking to reduce the time complexity, the space complexity, or looking for realworld reduction in time? If you are looking for the latter, making the implementation multithreaded and adding more processors as needed will reduce the real-world time significantly. Of course, if the original array or string is long enough, all the processors in the world wouldn't be enough to make a dent in the problem. Sep 9, 2016 at 17:33
• @MiguelvandeLaar The time complexity. Sep 10, 2016 at 2:21
• In the "for what it's worth department" here is a discussion of the Ruby::Array#purmutation method along with the `C` implementation thereof. But I don't see anything algorithmically embiggening. Sep 10, 2016 at 15:26

No, there is no efficient way to do this given the generality of your question. Since you haven't specified a class of properties, I'll let H be a cryptographic hash function into the natural numbers and let my property be "hashes to an even number under H".

We're assuming that H is difficult to invert (and that such functions exist), so the only way to tell whether a substring hashes to an even number is to hash it. To find the set of substrings that hash to even numbers, you must hash all of them. This is arbitrarily expensive, since I haven't specified H.

Data never just appears out of nowhere - it always comes from somewhere.

The most efficient way to determine the number of subarrays or substrings that have a certain property, is to have a "current count for property" that is updated whenever data/subarrays/substrings are created, are modified, are deleted, etc.

• For real world situations, this is often a good approach for creating caches or indexes incrementally, but from the theoretical point of view of the actual question, this still generates the set of all subarrays or substrings. Sep 7, 2016 at 6:28
• I agree, but is there some efficient way if you're just given the set of data? Sep 8, 2016 at 16:03

Assuming "if a string does not meet the condition, any of its substrings will not either", the solution could be close to the naive one. All you have to do is start checking the long substrings and if the condition is not met, skip checking the substrings of that substring:

``````private void Analyse(string s)
{
for (int i = 0; i < s.Length; i++)
{
string sub = s.Substring(i);
// do your stuff with the substring to analyse here,
// break if the condition is not met

for (int j = 0; j < sub.Length; j++)
{
string sub2 = sub.Substring(0, j + 1);
// do your stuff with the substring to analyse here,
// break if the condition is not met
}
}
}
``````
• Which is exactly what I did by starting out with "Assuming...". The accepted answer may be the only correct one but it is pretty useless to the OP so I figured this could be helpful. Sep 10, 2016 at 8:37
• Thanks for the concern. Zero votes so far (up or down). I'll take my chances :-). Sep 10, 2016 at 17:52