Find all substrings that contain k specific characters in a string

Question

Given a string, return the count of the number of substrings that contains characters A, B and C. Two substrings are considered different if the starting, ending or both positions differ.

Example - s = "ABBCZBAC", there are 13 substrings which are "ABBC", "ABBCZ", "ABBCZB", "ABBCZBA", "ABBCZBAC", "BBCZBA", "BBCZBAC", "BCZBA", "BCZBAC", "CZBA", "CZBAC", "ZBAC", "BAC".

My code in Java is giving timeout error for large inputs. my code is

public static long find(String s)
{
    for(int i=0;i<s.length()-2;i++)
    {
        int j=i+3;
        while(j<=s.length() && !(s.substring(i,j).contains("A") && s.substring(i,j).contains("B") && s.substring(i,j).contains("C"))
            j++;
        count += s.length()-j+1;
    }
    return count;
}

I tried to improve this code by finding indexes directly and storing them but still, I was getting timeout errors for large inputs. Can anyone give me a better approach to solve this question may be in O(n)?

Answer 1

The trick of these things is to:

1. create a model, and then
2. create a mathematical formula that uses the model.

If you look at the example string .A.B.C.A. then you can may first notice that it doesn't matter a bit if you substitute any other character than ABC for the dot. So we don't care a single iota what characters are at those locations.

Now we see a substring xA.B.Cyyy where A.B.C is just the shortest string in which all the characters are present. Any amount of characters x and y can be present, going from the A.B.C part to the outside. In other words, from this you can construct (#x + 1) * (#y + 1) = (1 + 1) * (3 + 1) = 8 separate substrings that contain this A.B.C. This set of substrings of course also includes xA.B.C.Ay, i.e. all longer substrings that contain the ABC.

Now lets look for substrings that are not covered: -axB.C.Ay. Here - and a are not actually part of the substring, it's just to indicate that we have to skip these characters to find a new ones. If we include the first A then of course we've already counted that substring before. So now we calculate that we need to add (#x + 1) * #y = (1 + 1) * (1 + 1) = 4 separate substrings. After that we cannot find a shorter alphabet (-a-bxC.Ay doesn't contain it). So there we are, we have 8 + 4 = 12 substrings that contain the alphabet.

In words: we have to continue looking for the next offset in the string, try to find the shortest alphabet, and stop if there isn't one. We need to keep track where the start of the last substring was that we found, to avoid duplicates. So there is your model and set of calculations.

As you can see, there is just one starting offset of the substring that increases to the right, and then we need to find the end offset within the string. In other words, the complexity is somewhere at O(N * 1/2N) ~ O(N). Easy-peasy for any modern computer.

However, the algorithm doesn't perform any contains! Heck, it doesn't even create the substrings that it just needs to count.

---

Another longer example for more visually oriented persons (where we count the pipe and dot characters):

ABBCZBAC
|  |.... -> 1 * 5 = 5
 BBCZBAC
 |    |. -> 1 * 2 = 2
 BBCZBAC
  |   |. -> 1 * 2 = 2
  BCZBAC
   |  |. -> 1 * 2 = 2
    ZBAC
    .| | -> 2 * 1 = 2
                   ==+
                   13

---

I'll post my code (made and thought of from scratch) iff you show you can do the same; post code and the answer for the following string (it should take the computer no time at all to calculate it).

CBZBBZABBBBAABZZZAZZBACBZCACCZCZABBACCAZCABCBBZBAZAACBZCABZAZCZZ

Probably better to create a new question for it. I don't even want to touch the current example.

Happy programming.

---

No time at all means:

AACZCBZACBZCBZZBCZBBBAABBCAACBCZZCCZABCCCZBAAACCBCBAZAZZBCAAABBCZBCZZZZZCZAZBZZZBCZCBBBCABZZBCCBBBBBCCCBAAZACAZZBCZBAZCBBACACCCZBBZAZAZBCZCZZCCCACCBAZAZBACAAAZCAZACBABZCZZBZACAZZZZACAZBCCABZCCCBAZZBZBAZZCCZCBBBBBBBCAABZCBCAACACCZBCABAZZAZZCZBZCACACZBZCZZBZZCCZZZZBBCCCCZBCCBZABZBAABZZZACZAABBZCABCZCABZAZCZCAZBBBACBCZACZAAZZACBZCCBZBZACCCBACAZACZAACAZAZBCCZBBZCZCZBACACAZBAZZAACCZZBZZZCAZZAAAABBBAZABBBBZAZZBACBBZAACBAZCCBBZCAZZAZAACAAZAZZBCBZCCCZCZCCZZAZABCBZBBZBBBBZZAAZZCABAAABBBBCZCCCCCABBZCBCACBZAZCBZBBAZZZCBCZZZAAAAAZCBABZCCCAZZAAAZAABABZBBAAZZACZAACABZZCBZABZZCACAAACAABAZBABBZBBBCAZAACACZAACAZCBCCBZCCCACBAZBBBZBBCZAAZCZCZBCABCZCBZABAZBAZZBCCZBBABCCCABZZZCBCBAZCBBBCAZZCBBAZBCCZBCCCABZZBZAZBBABACCBABZZCCBCAZBZZACBAZBCCAZZBAACZACZBZZBBBCAAZBBBABBAZBBZABCCBBBZBZZZAZABBZBACBCZAZBCZACBZBBZZBZABAZZBZCAABZBZBBZCCCAZABZCAZBBBZCZBBBZZBCBCCZAZZZABCBZZZCAABBBZCZZCBZZCZZZZACZBZCBCBBBZCCBZZBBCCZZCCCBZAAZZCZBBCBBCBZCAZCZZBBCBBZCZBAZBAAZCZABBCCZAACBBCBZACAZCCCBABBCZZZBZACZCZACZABCCZCCBBBBBCBZACCZZCAABZBCACCAAZZZCZBCAAZBZAZBZCAZBZCCCCZAZBBCCBBCZZCCAAACCZAABCZZAABBZBZZZAAAZABAACBCCBBCZCCBZCABAAABBAAABCBACBZZABZZBAZABCBZZBABBCACABBAZCBZBAZZZZZBACBZCCBCZZBAAZBBAABZCCZCACZAZZBACAZBABCZBBBAAZZCAZBBCCAZBCBCAAAZBZCCCZZZCAZCBBBBACCAZBCBBCCCBBCABZCCAZACZBABZBBCCCAZAACAAACZZAAACABCAAABAAABACAACCCZABZZZZZCBAABCCAAACACAAZCZCBZBZZZCCCBAZBAZZZCZBCCBZCCACCABCAAAABZCZABCBABZCZACCCACCCZZCCBCZBZZAABBZABCZBCZZZZCACBCBAZZBCAZABACZZABABZBZZCBCACAZACAZZZBBBCCABABZBCAZZCBACACABCAZCCACZBBCCAACCBBCBABZZAZCAABAZAACZZBCCBAACCCCAACCBAZBAZCAABBZZBAZZZBBZZBZAABCCBCBZZCZZABCCZBZCACCZAABCAZBBCZACCZBZBBCZCZCAZZBAAZZZAABBAZZZBZCCZCABZBZCZCCAZAZCBAACCAZZCZBBCCACAABBBZZBZZZAACBZCAAZCBZZAZZBBCCZBBAAZAAZZZZBCBCBCBBACCCCZCACZAACZCCAAZAABCZCCZABCZBBCAAACCBCCABZACBACAAAZCBBACAACCCZACCABBACCBABZZBCACCZZACBBAZZCBABBZBAACCCAZAZAZZCCCCCCZCAACAABBZABCZAAZCCBZZZAZCBCAZACCAZBBCZZAZZCABCAZCBZAZABCBZACZCZAAZZZBZZZZZAZZCBZBBZZABABABAAAAZZZACZAZZZZZBBACZCZBZBAAZAAZCCCAZCZZCABCCABBZZBCACCCBBCCCAZCBABBZCBBBAZCBCZBCAZZCBZZAZBBCZABACCZACBABZCBCBZBAACCZBZAZACBBZZZZBBBBZZZAZBAABCCCZCCAZBCAABCAAZACCBZBCCZZABCABABBBBBBCZCBZACBCAABBBCCCZAABCBZBCAZAZZABZAZZCZZAZBAAAAACZZACZCACCZABACAZAACZCCAZABAACBZCABCCAZACCBBZBBZBZZCCZBAABZBBBBCAZAZZACZABABBZCZZZBZBBCBBAZZZBABAAZZBABZBCBAAZCACAACCZAABZZZBBBZACZCCCZABBBCCCBZACZCCZZAZCBABCCACZABCAZZCBZZCBBBCAZZABBABCZZBCABZBAAAABCCAAZABBZZZZZAABBBAZBCACABZACCCBBBZABZBAZAZBAAZAZCAZAZZBBZBCCCCZCZCBAZBCABZCZAACZAZACBABAAZBCBBACACBZCAZCCBZBZBZABCCZBCZCAZAAZCACCCBCBZZZCZBCBCAZBAAZCACAABZBCBBZZBBZBCABZABCCBCAZBAZCBAAZBZAZZZBCZCCBCCACAZBZZCCAZCACAZZCABCBCZCABBCZBBCZCBCBZACBZAACCBZACBZACCBCBZACACBCAZZZZCCZBCZACCACZACZCBCABCCABZAZCABCCCAACZCBZABZZCABBZBCCAABABAZBCZBBABCAZZCBABABZZACBZBBCBBCBZCBCZBCCZZCBABACABBAAABCCCACCABAABBBZZCCCZABZCZZBABCCCBCBZAZBABCZBZZZCABCZBZCBACCBAABABAZBAZACZBAACBAZZBABCZCBZCCAAZACACZCAAACBCBBABACACCCAZBZCCACBBZCCACAZBAZCACACZCZBCZBBBAAZBAZZZACCCCCCCAAZAZCAAAZBZZZCZCZBCBZZCZAACACCBAAABZZZBZZZACBZAABABCBAACAZCCZBZZCZACABCAZZABBCCAAAABAACABAZZACZZBZBAZZCACACBBCACAZCZZBZCACCZACCCABZCAZABCZZACAZACZAABBCZAZZABZCZCCZCZCZCAACACCCAZCCBZZCAZBACCZCBBZAABBAAAZACAAACBCCZAACBZBBBCACZZCZZCCCBZCBAAZCCCCACCZCZCZBZBZZCZCCBBZCAABBAABAACAZZBCACZZABBAZZBZZCBBAACBZAAABZAABBAZCZBZABBBBBCZBBCABABBBZZZABBAAABCCCZBCAAAZABZCBBACCAAZAABZCBCZBCABABCBCZCZCAACACCZZCCCBZZBCABAABABZBACAZBZBABBZCABZBBCACBBZCZABBZCZAZZZABZCZZBAACZZCZACBZBCZCCABCAAZBACCZCAACZBBACZCZCCBCBABBCZZBABZBBACACZZAACCCCCCZCBACCACZZZBACZZZBZCACBBCZCBBCAZBCACBCBBBCAACBZACAAZAACBCCZZZABCBCCAZBBBBCZBBACZCAZACZBBABABZCCZBCCACBAABBZAAACZAABZZCAZAABBBCABCCCACACCBABZCCZBBBAZCCAZZBBZZAZCABBZCCZAACZAZZCBBZABCACBZBCBCZZZBBACBBCAZABAACAZBBBAZBCBCBAACBAZBAAZZBZACBZBACZBZCCABZZCBAZZBCZBCCCZACAZAZCABAACAABBZZBAAACABZAAZBCACBACABACBCBZABCCACBBZBBZBAZCCBCCCABZZCBCZZAAZCCCCAZZACCZZCBZCZZZCAZZABZAZZACCABZABCCAAAAAABZBCCZCBBZCCZAZAACACBBBBCAZABZCBCZABZCBAAACCZBBBCBZCAAAZCZAACBAZZZZABCZCABAABZZAACCCAZZZCZAACZACCCZBACCBBBBZACZBBAZZABZACAZBAZCBCACACAAACBCBAZCCBZBBZAABAZZCCCCBACBZBCCBACZABZBZBZACABBBZBCAZZBCBBCZABCZBBBZZCCAAZBBAZCAZBAAZAAZZBBCCZABCZAAZBCACCCBABCZBCACZAABBBACCZBBABBCZACAZZAZCBZCCAACBZCBABZAZBCAZBCBCZBZBBABZZCBZAAZ

gives

8364211

instantly. Feel free to check that answer.

In under 2 minutes, I can have an answer for a 1 billion sized character string:

499999994166624150 substrings
116292 ms