Problem Statement
You are creating a new chat software called Happy Messenger. The defining feature of your chat is that it will allow users to post only messages representing the happy state of mood. If a certain message does not look happy, it will automatically be modified into a happy one before being posted.
Of course, it is very difficult to actually understand whether a particular message represents a happy state of mood or not. Therefore, you've decided to limit yourself to a rather simple heuristic analyzer based on emoticons. Given a string, you extract all its maximal consecutive substrings that either consist of '('s only, or consist of ')'s only. For each such substring that contains X characters ')', you add X^2 to the string's score, and for each substring that contains X characters '(', you subtract X^2. If the final score is strictly positive, then you consider the string to be happy, otherwise it is not happy.
For example, strings "hello :)" (score: 1) and "sorry (( but that's still so funny :))))" (score: 12) are happy, while strings "boring" (score: 0) and "really sad :((" (score: -4) are not.
In order to make a message happy, you are allowed to insert arbitrarily many characters into any positions in the message (including the beginning and the end). Any other modifications (for example, character removal or replacement) are not allowed.
Given a String msg, find and return the minimum number of characters that we need to insert in order to transform it into a happy string. If msg is already happy, return 0.
Of course, it is very difficult to actually understand whether a particular message represents a happy state of mood or not. Therefore, you've decided to limit yourself to a rather simple heuristic analyzer based on emoticons. Given a string, you extract all its maximal consecutive substrings that either consist of '('s only, or consist of ')'s only. For each such substring that contains X characters ')', you add X^2 to the string's score, and for each substring that contains X characters '(', you subtract X^2. If the final score is strictly positive, then you consider the string to be happy, otherwise it is not happy.
For example, strings "hello :)" (score: 1) and "sorry (( but that's still so funny :))))" (score: 12) are happy, while strings "boring" (score: 0) and "really sad :((" (score: -4) are not.
In order to make a message happy, you are allowed to insert arbitrarily many characters into any positions in the message (including the beginning and the end). Any other modifications (for example, character removal or replacement) are not allowed.
Given a String msg, find and return the minimum number of characters that we need to insert in order to transform it into a happy string. If msg is already happy, return 0.
Definition
- Class:
- HappyString
- Method:
- makeItHappy
- Parameters:
- String
- Returns:
- int
- Method signature:
- int makeItHappy(String msg)
- (be sure your method is public)
Constraints
- msg will contain between 1 and 50 characters, inclusive.
- Each character in msg will be a letter ('a'-'z', 'A'-'Z') or one of '(', ')', ' ', '.', ',', '!', '?', '-', ':', '''.
Examples
"Very happy about going to TechOlympics ! :))"
Returns: 0
This message is already happy."Let's do some math: (2 + 2) * (2 + 2) = 16."
Returns: 1
The score of this string is 0. It's enough to insert one ')' character into any position to make it happy.":-((("Returns: 3
One possible solution is ":-()))((". The score of this string is -1+9-4 = 4."( ( ) ( ( )"
Returns: 1
"())((())))((((("Returns: 2
There are 5 substrings that influence the score: "(", "))", "(((", "))))" and "(((((". Hence the score of this string is -1+4-9+16-25=-15 and the string is not happy. We can insert two ')' characters right after the end of the "))))" substring. Now the score is -1+4-9+36-25=5 and the string is happy."(())(()((((("Returns: 4
"((((((((((()))))))()))))((())(((((((()()(((((((((("Returns: 7
"MSVEP(((((((())))((((((v'(((XWoRXniG,CP((()((((B(("Returns: 8
Back to all problems