I recently solved this very interesting problem while practicing for the upcoming Usaco competition in two weeks. Here is a link to the problem if you would like to read it for yourself. In summary, the problem gives you a string s, and asks you to return the sum of the number of occurrences of the string ‘bessie’ across all substrings of the given string. Not only this, the substrings of bessie can be created by ignoring certain letters in the given string. To use the example given, if the substring is ‘bqessiyexbesszieb’, you would say it has two occurrences of ‘bessie’ since when you ignore the interspliced letters, you see it reads ‘bessiebessie’.
To solve this I first solve the sub-problem of identifying the number of times bessie occurs in the string. One simple way to solve this is to scan through the string and build a new copy of the string, but only append the letters needed to spell bessie like b, e, s, and i. This way, when building the string for the previous example, all unnecessary letters will be filtered out leaving only what you need. However, what if the string is ‘bessbessie’? In this case we would like the program to ignore one of the ‘bess’. To do this we can add another stipulation that states that the next letter added has to not only be contained in the spelling of bessie but contribute to spelling it. This way when the scanning reaches the 5th letter, it will see that the string it has currently built spells ‘bess’ and needs an I to continue, and thus ignore all other letters including the second occurrence of ‘bess’.
Notice that this method only needs to keep track of what the next letter should be while scanning. We can use this observation to apply this method to all substrings simultaneously while scanning. To do this, simply use a 6 dimensional array, where the ith value represents the number of substrings that need the ith letter next. This way, when you scan the letter b, you move all those values in the first slot to the second, since as their need for the first letter has been satisfied, they are now waiting for the second slot. you do this by adding the values in slot 1 to slot 2 and then set slot 1 to 0. You do the same for the letter e, but you update for both slots 2 and 6 as they both use e. Notice that when updating for the last letter, this means that the substrings has finished spelling bessie, so you can add the value in the last slot to the first slot instead. Lastly, add that same amount to a counter as well, as those have all finished counting.
We now have a way to update all the substrings at once, but now do we do we account for all substrings? Each time we move onto a new letter, we can add one to the first slot, since this would be equivalent to adding a substring that starts at the ith position. Then, at the end of every step, we can add the sum of all past answers to an additional counter to represent all the substrings that began at all the values from 0 to i and ended at i.
I found this solution very interesting since it takes a seemingly complex problem with many sub problems and finds a way to solve for everything at the same time, while accounting for all scenarios. By noticing that the only thing that was kept track of in each sub solution was a single variable, it allows you to do something like this. Though I was unable to come up with this solution myself, I wanted to share this because I believe cool solutions like this are a testament to what makes CS such an interesting subject.
I know my explanation was far from clear, I am working on it. In the meantime, here is my code with some notations:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class pareidola2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
long[] arr = new long[6]; // array to keep track of substring endings
long ans = 0; // counter of final answer
long past_ans = 0; // counter of all past answers
for (int i = 0; i < s.length(); i++) {
arr[0]++; // arr[0] is the number of substrings that are currently waiting for a b
// I added one to it to represent adding a new substring that begins at i.
switch (s.charAt(i)) { // switch statements are cringe I know.
case ‘b’: // move from 0 to 1.
arr[1] += arr[0];
arr[0] = 0;
break;
case ‘e’: // 1->2 and reset 5’s
arr[2] += arr[1];
past_ans += arr[5];
arr[0] += arr[5];
arr[1] = arr[5] = 0;
break;
case ‘s’: // 3->4, 2->3 in this order.
arr[4] += arr[3];
arr[3] = arr[2];
arr[2] = 0;
break;
case ‘i’: // …
arr[5] += arr[4];
arr[4] = 0;
break;
}
ans += past_ans; // add for all substrings that ended at i.
}
System.out.println(ans); // we get an ans that is the sum of all substrings.
}
}
Lingyuan's blog 