why did we have to multiple 2 by the count of the string containig three ABBA in last exaxmple of last class?
top of page
OLYMPIAD EDUCATION
Our students test on average 78% better then nationwide averages in International and Canadian Academic Competitions: CMC, CCC, COMC, CMO etc.
Give your child a chance to succeed in Canadian Mathematical Competition, Canadian Computing Competition and International Math Competition!
​Schedule a Consulting Session today!
Call Now: 587-331-9779 647-375-6881
Email: info@olympiadedu.org
Contest Course In-classroom or On Line Across Canada !
bottom of page
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.