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 ...read more

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’.

O( X + Y + Z ), where ‘X’, ‘Y’, ‘Z’ are the given maximum number ‘a’, ‘b’, and ‘c’ respectively that the output string can have.

In the worst case, we need to store a string of size ‘X + Y + Z ’, that takes O (X + Y + Z) space. Although we are using a heap data structure, but we will only store 3 elements that take constant space.  Hence the space complexity will be O (X + Y +Z).

O(X + Y + Z),  where ‘X’, ‘Y’, ‘Z’ are the given maximum number ‘a’, ‘b’, and ‘c’ respectively that the output string can have.

We are adding at most 2 characters to the string on each iteration, So in the worst case loop will run (X + Y + Z)/2 times which takes O( X + Y + Z) time. Although we are using heap data structure, in which push and pop operation takes O( log(N) ), where ‘N’ is the number of elements in the heap. time, but we will only store 3 elements so that takes constant time.

Hence, the overall time complexity will be O(X + Y + Z).

'''

    Time Complexity: O(X + Y + Z)

    Space Complexity: O(X + Y + Z)



    where 'X', 'Y', 'Z' are the given maximum number 'a', 'b' and 'c' respectively that output string can have. 

'''



from heapq import heappush, heappop





def happyString(x, y, z):

    maxLength = x + y + z



    # Declare an empty string to store final resultant string.

    result = []



    # Create a char array to map 0 -> 'a', 1 -> 'b' and 2 -> 'c'.

    charMap = ['a', 'b', 'c']



    # Declare a max heap to store available count of characters.

    maxHeap = []



    # Push given count of 'a', 'b' and 'c' if they are non zero.

    if x > 0:

        heappush(maxHeap, [-x, 0])



    if y > 0:

        heappush(maxHeap, [-y, 1])



    if z > 0:

        heappush(maxHeap, [-z, 2])



    # Run a loop until heap contain at most 2 elements.

    while len(maxHeap) >= 2:



        # Pop first two elements from the heap.

        first = heappop(maxHeap)



        second = heappop(maxHeap)



        first[0] *= -1

        second[0] *= -1



        # Add the character with maximum current count two times if possible.

        for i in range(2):

            if first[0] != 0:

                result.append(charMap[first[1]])

                first[0] -= 1



        # If count of second popped element becomes more than count of first, then add this character two times.

        if second[0] > first[0] and second[0] > 2:

            result.append(charMap[second[1]])

            result.append(charMap[second[1]])

            second[0] -= 2

        else:

        # Else add second character one time only.

            result.append(charMap[second[1]])

            second[0] -= 1



        # If count of first and second element do not become zero then push them back into the heap.

        if first[0] > 0:

            heappush(maxHeap, [-first[0], first[1]])



        if second[0] > 0:

            heappush(maxHeap, [-second[0], second[1]])



    # If heap still contain one element then we can add this character at most 2 times.

    if len(maxHeap) != 0:

        first = maxHeap[0]

        first[0] *= -1



        for i in range(2):

            if first[0] != 0:

                result.append(charMap[first[1]])

                first[0] -= 1



    # Return resultant string.

    return result

/*
    Time Complexity: O(X + Y + Z)
    Space Complexity: O(X + Y + Z)

    where 'X', 'Y', 'Z' are the given maximum number 'a', 'b' and 'c' respectively that output string can have. 
*/
    
import java.util.*;

public class Solution {
    public static String happyString(int x, int y, int z) {
        int maxLength = x + y + z;

      // Declare an empty string to store final resultant string. 
      StringBuilder result = new StringBuilder();

      // Create a char array to map 0 -> 'a', 1 -> 'b' and 2 -> 'c'.
      char[] charMap = new char[]{'a', 'b', 'c'};
      
      // Declare a max heap to store available count of characters.
      PriorityQueue maxHeap = new PriorityQueue(2,new Comparator() {
          public int compare(int[] o1, int[] o2) {
              // Intentional: Reverse order for this demo
              return o2[0]-o1[0];
          }
      });

      // Push given count of 'a', 'b' and 'c' if they are non zero.
      if( x > 0)
      {
          maxHeap.add(new int[]{x, 0});
      }

      if( y > 0)
      {
          maxHeap.add(new int[]{y, 1});
      }

      if( z > 0)
      {
          maxHeap.add(new int[]{z, 2});
      }

      // Run a loop until heap contain at most 2 elements.
      while (maxHeap.size() >= 2)
      {
          // Pop first two elements from the heap.
          int[] first = maxHeap.peek().clone();
          maxHeap.remove();

          int[] second = maxHeap.peek().clone();
          maxHeap.remove();

          // Add the character with maximum current count two times if possible.
          for(int i = 0; i < 2; i++)
          {
              if(first[0] != 0)
              {
                  result.append(charMap[first[1]]);
                  first[0]--;
              }
          }

          // If count of second popped element becomes more than count of first, then add this character two times.
          if( second[0] > first[0] && second[0] > 2)
          {
              result.append(charMap[second[1]]);
              result.append(charMap[second[1]]);
              second[0] -= 2;
          }

          // Else add second character one time only. 
          else
          {
              result.append(charMap[second[1]]);
              second[0] -= 1;
          }

          // If count of first and second element do not become zero then push them back into the heap.
          if(first[0] > 0)
          {
              maxHeap.add(first);
          }
          
          if(second[0] > 0)
          {
              maxHeap.add(second);
          }
      }

      // If heap still contain one element then we can add this character at most 2 times.
      if( maxHeap.size() != 0)
      {
          int[] first = maxHeap.peek().clone();

          for(int i = 0; i < 2; i++)
          {
              if(first[0] != 0)
              {
                  result.append(charMap[first[1]]);
                  first[0]--;
              }
          }
      }

      // Return resultant string.
      return result.toString();
    }
}

    

/*
    Time Complexity: O(X + Y + Z)
    Space Complexity: O(X + Y + Z)

    where 'X', 'Y', 'Z' are the given maximum number 'a', 'b' and 'c' respectively that output string can have. 
*/

#include

string happyString(int x, int y, int z)
{
    int maxLength = x + y + z;

    // Declare an empty string to store final resultant string. 
    string result = "";

    // Create a char array to map 0 -> 'a', 1 -> 'b' and 2 -> 'c'.
    vector charMap = {'a', 'b', 'c'};

    // Declare a max heap to store available count of characters.
    priority_queue> maxHeap;

    // Push given count of 'a', 'b' and 'c' if they are non zero.
    if( x > 0)
    {
        maxHeap.push({x, 0});
    }

    if( y > 0)
    {
        maxHeap.push({y, 1});
    }

    if( z > 0)
    {
        maxHeap.push({z, 2});
    }

    // Run a loop until heap contain at most 2 elements.
    while (maxHeap.size() >= 2)
    {
        // Pop first two elements from the heap.
        vector first = maxHeap.top();
        maxHeap.pop();

        vector second = maxHeap.top();
        maxHeap.pop();

        // Add the character with maximum current count two times if possible.
        for(int i = 0; i < 2; i++)
        {
            if(first[0] != 0)
            {
                result.push_back(charMap[first[1]]);
                first[0]--;
            }
        }

        // If count of second popped element becomes more than count of first, then add this character two times.
        if( second[0] > first[0] && second[0] > 2)
        {
            result.push_back(charMap[second[1]]);
            result.push_back(charMap[second[1]]);
            second[0] -= 2;
        }

        // Else add second character one time only. 
        else
        {
            result.push_back(charMap[second[1]]);
            second[0] -= 1;
        }

        // If count of first and second element do not become zero then push them back into the heap.
        if(first[0] > 0)
        {
            maxHeap.push(first);
        }
        
        if(second[0] > 0)
        {
            maxHeap.push(second);
        }
    }

    // If heap still contain one element then we can add this character at most 2 times.
    if( maxHeap.size() != 0)
    {
        vector first = maxHeap.top();

        for(int i = 0; i < 2; i++)
        {
            if(first[0] != 0)
            {
                result.push_back(charMap[first[1]]);
                first[0]--;
            }
        }
    }

    // Return resultant string.
    return result;
}

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 st...read more