Longest Happy String

Given 'X', 'Y' 'Z' you can try all combinations of possible strings and return the string that has a maximum length. You can create all possible strings by inserting all the three letters i.e. ‘a’, ‘b’, ‘c’ at each ‘i -th’ position in string by taking care of the condition that no three characters should be the same. For example at ‘i -th’ position in the string you can add the letter ‘a’, if and only if 'X' greater than 0 and the last two letters in string i.e. at position ‘i - 1’ and ‘i - 2’ are not ‘a’. Similarly of ‘b’ and ‘c’. At last check all the possible strings you generated and return the string with the maximum size.

Algorithm:

• Declare a global empty string, say 'ANSWER'.
• Create a function say 'FIND_LONGEST' to generate and find the maximum possible string.
• Create a function say ‘check’ to check if a character can be added in a string or not.
• Call 'FIND_LONGEST' with given 'X', 'Y', 'Z' and 'ANSWER'.
• Return answer.

Description of ‘check’ function

The function will take two parameters:

• 'STR': Current string.
• ‘c’:  character to add.

bool check( 'STR', ‘c’ ):

• If the size of 'STR' is less than 2, then we can add any character, So return true.
• If last two characters are same as ‘c’, then return False,
• Else return True.

Description of 'FIND_LONGEST' function

The function will take four parameters:

• ‘X’ : The maximum number of ‘a’ can be added.
• ‘Y’ : The maximum number of ‘b’ can be added.
• ‘Z’ : The maximum number of ‘c’ can be added.
• 'STR': Current string.

void findLongest ( ‘X’, ‘Y’, ‘Z’, 'STR' ):

• If the size of 'STR' is greater than the size of 'ANSWER', then update answer.
  • 'ANSWER' = 'STR'
• If ‘X’ > 0 and check('STR', ‘a’) is true i.e. we can add ‘a’ to current 'STR'.
  • Recursively call ‘findLongest (X - 1, Y, Z, 'STR' + ‘a’ )’.
• If ‘Y’ > 0 and check('STR', ‘b’) is true i.e. we can add ‘b’ to current 'STR'.
  • Recursively call ‘findLongest (X, Y - 1, Z, 'STR' + ‘b’ )’.
• If ‘Z’ > 0 and check('STR', ‘c’) is true i.e. we can add ‘c’ to current 'STR'.
  • Recursively call ‘findLongest (X, Y, Z - 1, 'STR' + ‘c’ )’.

Let’s start with an empty string and gradually add available characters in it, as we wanted to maximize the length of string, so we greedily add that character whose current availability is maximum i.e current limit is highest. We cannot add three consecutive same characters, thus we add that character two times only and then find the next different characters with maximum availability and that character.

For example, if we have 5 ‘a’, 3 ‘b’, 1 ‘c’. 

• We start with an empty string let say ‘S’.
• Then we add 2 ‘a’ to ‘S’ because the availability of ‘a’ is maximum.
• Now ‘S’ becomes - ‘aa’ and the count of ‘a’ decreases to ‘3’ as we have used 2 a’s.
• Next, we add 1 ‘b’, as the next maximum available different character is ‘b’.
• Now ‘S’ becomes - ‘aab’.
• Again ‘a’ is available more than others so we add 2 ‘a’ to ‘S’ i.e ‘aabaa’.
• But now count of ‘a’ become 1 while count of ‘b’ is 2 which is maximum so now we add 2 ‘b’ that make ‘S’ “aabaabb”.

We repeat this process until either all available characters are used or we end up with only one type of character. We can use max heap data structure to get max available character after each update.

Algorithm:

• Let the 'X', 'Y', 'Z' be the maximum availability  of ‘a’, ‘b’, ‘c’ characters respectively.
• Declare an empty string say ‘S’ to store the answer string.
• Declare a max heap to store three characters ‘a’, ‘b’, and ‘c’ with their availability such that the top element in the heap has a maximum value.
• Push { 'X', ‘a’}, {'Y', ‘b’} and {'Z', ‘c’} into the heap, if 'X', 'Y', 'Z' respectively are nonzero.
• Run a loop until the size of the heap is greater than 1.
  • Pop 2 elements from the top of the heap and store these two in variables say 'FIRST' and 'SECOND'.
  • If the count of  'FIRST' element is greater than 2.
    • Add 'FIRST' character 2 times in ‘S’
    • Decrease count of 'FIRST' by 2.
  • Else, add 'FIRST' character 1 time in ‘S, and decrease its count by 1.
  • Now check if the count of 'SECOND' becomes more than the count of 'FIRST', then add 'SECOND' char 2 times, and decrease its count by 2.
  • Else add 'SECOND' character 1 time, and decrease its count by 1.
  • If  the count of 'FIRST'  > 0
    • Push 'FIRST' back into the heap.
  • If the count of 'SECOND' > 0
    • Push 'SECOND' back into the heap.
• If the size of the heap is 1
  • it means that only one type of character is left, So add min(count in top element in heap, 2) to ‘S’.
• Return ‘S’.

Suppose there are only two characters available and say only ‘a’ and ‘b’ with count 'X' and 'Y'. Also, suppose that 'X' is very high than 'Y'. Then to maximize the size of the string. We construct a string like this - “aabaabaab...”. We can extend this greedy approach to three characters. The idea is to keep track of currently available characters and add the most available character till we can add i.e. we can add at most two times consecutively and then add any of the other two characters. We can do this iteratively by keeping track of count current available characters and the last two characters in the string. In case there is only one type of character is left i.e count of the other two characters becomes 0, and the last two letters in the string are the same as the character that is left, then we cannot increase the size of the string further.  

Algorithm:

• Let the 'X', 'Y', 'Z' be the maximum availability  ‘a’, ‘b’, ‘c’ respectively.
• Declare an empty string say ‘S’ to store the answer string.
• Run a loop till (x + y + z)
  • If ( 'X' >= 'Y' and 'X' >= 'Z' and the last two letters in ‘S’ is not “aa” ) or ( the last two letters in ‘S’ are “bb” or “cc” and 'X' is nonzero).
    • Add ‘a’ to ‘S’, and update 'X' to ‘x - 1’.
  • If ( 'Y' >= 'X' and 'Y' >= 'Z' and the last two letters in ‘S’ is not “bb” ) or ( the last two letters in ‘S’ are “aa” or “cc” and 'Y' is nonzero).
    • Add ‘b’ to ‘S’, and update 'Y' to ‘y - 1’.
  • If ( 'Z' >= 'Y' and 'Z' >= 'X' and the last two letters in ‘S’ is not “cc” ) or ( the last two letters in ‘S’ are “bb” or “aa” and 'Z' is nonzero).
    • Add ‘c’ to ‘S’, and update 'Z' to ‘z - 1’.
• Return S.