Day 18 | Dominant Character | C++

I had fun solving this problem today. Don't forget to try it yourself.

Problem Link

This problem teaches us that pen and paper (or digital equivalent) is the best friend of a person solving a DSA problem.

This problem discouraged me a little because despite solving tons of questions, I had no idea about how to go about this problem. So I started with one thing, that you must do in contests if nothing is coming up in your mind - start creating test cases for different answers.

Let's start writing for the cases -

Answer is 1

Not possible

Answer is 2

Only substring aa can be possible for the answer to be 2

Answer is 3

Possible Substring- 'aba', 'aca'

Note: If the answer was 'caa', then the answer would be 2 because 'aa' substring is there.

Answer is 4

Possible substring - 'abca', 'acba'

After writing it for answer = 4, I realized that since there are two 'a' and one 'b' and 'c'

Now for answer > 4

We have let's say two 'b' (or 'c') between two 'a's

like this 'abba',

Now we need more 'a's, but if I append 'a' directly after 'a' answer will become 2 because 'abba' will become 'abbaa' which contains 'aa'

and if I add 'ba' or 'ca', then it will become 'abbaca', which will have an answer = 'aca' hence 3

Now, the only option is to add 'cca', making it 'abbacca', thus creating an answer for 7. But if we follow the same steps to try to create an answer greater than 7, it won't be possible.

This is called the greedy approach (at least I call it that) because for some small set of data, my approach makes sense. We generally prove our greedy approach before submitting, but I also test my greedy approach by submitting it (LOL)

But we will prove our math here

Proof

Let's say we have a substring that matches our criteria and have X ( > 7) 'a's

Now we know that there are at max one 'a' sandwich with two 'b' or 'c's

because if they were not, the answer would become 7 as we discussed above

So, let's consider our substring like this abba??a??a??a

In the first sandwich, 'a' count equals to 'b' count, and if we keep adding 'b' further equally, then we will be increasing 'b' wrt to 'a', thus count of 'a' will never be greater than 'c'

Hence answer can never be greater than 7.

Hence answer is only possible for values 2,3,4 and 7.

How to use our prove for an answer?

Since we know that the answer will be limited, we can run a sliding window approach and check for windows of each length.

You can find my implementation here.