Light OJ 1051-Good or Bad

Jan’s LightOJ :: Problem 1051

Abridged Problem: A string is called bad if it has 3 vowels in a row, or 5 consonants in a row, or both. A string is called good if it is not bad. You are given a string s, consisting of uppercase letters (‘A’-‘Z’) and question marks(‘?’). Return “BAD” if the string is definitely bad (that means you cannot substitute letters for question marks so that the string becomes good), “GOOD” if the string is definitely good, and “MIXED” if it can be either bad or good.

Firstly, can we solve the problem with Brute force, Yes? Yes! Absolutely. For every position with “?” character we have two choice, one is vowel and another is consonant. So, we can iterate over using vowel and constant, and find the solution.

But Alas! for each string it will be given of length up to 50 characters. So, the complexity for the problem will be 250∗TestCase250∗TestCase. So, it’s quite impossible to run in 1s or 2s. So, what can we do now! Is it impossible!

No! Think wisely and deeply. Some state will repeat over a while.

Let, we had given the string: “??A??”. We can draw a tree by choosing vowel or constant. Please look at the figure below:

In the figure above, I used A as vowel representation and C as constant representation.

Tree is drawn with some node. You can see that the red circle string will repeated. So, we can skip this as it repeated.

If you understand this, you can now think more about the problem otherwise read the passage again.

• Now, I will describe the DP states in briefly,

  1. Present Position where I am,
  2. The previous character from which I came from,
  3. Number of vowel counted that are contiguous,
  4. Number of consonant counted that are contiguous.
  

So, thats all, Happy Coding!

Follow my blog for new updates!