1

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 '16 at 13:56
  • You need to exploit the specifics of the property you're interested in to beat the naive solution. – CodesInChaos Sep 9 '16 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. – Miguel van de Laar Sep 9 '16 at 17:33
  • @MiguelvandeLaar The time complexity. – foobar1209 Sep 10 '16 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. – radarbob Sep 10 '16 at 15:26
6
+50

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.

2

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.

  • 2
    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. – Doc Brown Sep 7 '16 at 6:28
  • I agree, but is there some efficient way if you're just given the set of data? – foobar1209 Sep 8 '16 at 16:03
0

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. – Martin Maat Sep 10 '16 at 8:37
  • Thanks for the concern. Zero votes so far (up or down). I'll take my chances :-). – Martin Maat Sep 10 '16 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.