How to check if a String contains a substring in any order?

Question

This is not same as "How to check if a string contains s specific substring?" . I found a no of questions like that here but not precisely what i am looking for. I am creating a program at a competitive coding site the problem of which states that we are given a string made of x,y,z and we have to count the number of substrings which contains atleast one of those chars but not all of them.I tried this...

    String text = sc.next();
      int l = text.length();
      int count=0;
     for(int j =1;j<=l;j++)
      {
     for(int i1 =0;i1<j;i1++){
        String g = text.substring(i1,j);
        if(g.contains("xyz")||g.contains("xzy")||g.contains("yzx")||g.contains("yxz")||g.contains("zxy")||g.contains("zyx"))
        ;
        else
        count++;




      }

      }
      System.out.println(count);

And this worked(atleast for 2 test cases). But for the larger test cases my program is violating the time limit. Now i think that is because of the number of matching conditions in the if clause. I would like to know if there is any way by which i can just check if the substring contains 'xyz' in any order instead of checking for every order.Thanks! Any help is appreciated.

P.S- If anything else is responsible for the time limit violation, do mention out !

Answer 1

Here is a simple solution. Warning untested code!

String target = ...

String text = sc.next();
if (target.length() == 0) {
    // matched!
} else {
    for (int i = 0; i <= text.length() - target.length(); i++) {
        if ((pos = target.indexOf(text.charAt(i))) >= 0) {
            boolean[] found = new boolean[target.length()];
            found[pos] = true;
            int matchCount = 1;
     outer: for (j = 1; j < target.length(); j++) {
                pos = 0;
                while (true) {
                    pos = target.indexOf(text.charAt(i + j), pos);
                    if (pos == -1) {
                       break outer;
                    } else if (!found[pos]) {
                       found[pos] = true;
                       matchCount++;
                       break;
                    }
                }
            }
            if (matchCount == target.length()) {
                // matched!
            }
        }
    }
}

If you wanted to make this faster, one possibility is to clear and recycle the found array that we are using "mark off" the characters as we match them.

There may be more significant optimizations. However, I don't think that the Boyer-Moore "trick" of skipping a number of characters is going to work here.

UPDATE

Your original solution is O(N factorial(M)) where N is the text length, and M is the target string length.

My solution is O(N M).

The optimal solution involves calculating a running hash by multiplying prime numbers, as described in one of the answers to How to find all permutations of a given word in a given text?. I think it is O(N) on average.

(Hint: the solution I'm referring to as written looks like it is O(M N). However, we should be able to use the inverse multiplication equality:

((ab mod n) . (b^-1 mod n)) mod n = a mod n

where a and b are the prime factors and n is 2³² or 2⁶⁴ depending on whether we use int or long. Reference: wikipedia.

This will allow is to "multiply in" and then "inverse multiply out" the characters and therefore update the running hash in O(1) operations.)