I was asked to design 10 flags with vertical stripes using three colors: blue, orange, yellow. I was asked not to have two neighboring stripes of the same color (as a two-striped flag with two blue stripes looks exactly the same as a one-striped blue flag). I was also asked not to have yellow and orange stripes next to each other as it doesn't look nice. My goal was to minimize the number of stripes I need to use. So, I can make 3 different one-striped flags. I can make 4 different two-striped flags: blue-yellow, blue-orange, yellow-blue, orange-blue. I can make 6 different three-striped flags: blue-yellow-blue, yellow-blue-yellow, orange-blue-orange, blue-orange-blue, orange-blue-yellow, yellow-blue-orange. That is, I can make 13 different flags using 3 stripes at most.
Your task is, given the number of flags, numFlags, and a String forbidden describing the colors that may not neighbor each other, return the minimum number of stripes you need to design the given number of different flags using at most that amount of stripes.
In more detail:
A String forbidden will be constructed in the following manner:
- the colors will be indexed from 0
i-th element of forbidden will be the indices of colors that are not allowed to be neighbors of the i-th color
each element of forbidden will be a single-space delimited list of numbers without trailing/leading spaces
each element of forbidden will have numbers without leading zeroes in increasing order
each color will be in the list of forbidden colors of itself
rules for forbidden colors are symmetric: if the i-th color can't be a neighbor of the j-th color, then the j-th color can't be a neighbor of the i-th color
at least one pair of neighbors will not be forbidden (if all possible pairs are forbidden, then you can only make one-striped flags)