why did we have to multiple 2 by the count of the string containig three ABBA in last exaxmple of last class?
OLYMPIAD EDUCATION
Give your child a chance to succeed in Canadian Mathematical Competition, Canadian Computing Competition and International Math Competition!
Our students test on average 78% better then nationwide averages in International and Canadian Academic Competitions: CMC, CCC, COMC, CMO etc.
because ABBABBABBA contans three substrings ABBAs
so it was included three times in the orginal count 448:
ABBAxxxxxx
xxxABBAxxx
xxxxxxABBA
we only can keep one in our counting so we have to subract two times the number of ABBABBABBA. Similiarly, strings containing two ABBAs with overlap and strings contaiinng two ABBAs without overlap were included in the orginal 448 for two times, so we only subscract once. 448-23-20-2*1 = 393
This question is a very good question to practice how to remove overcounts.