Longest Happy String in C++

Suppose there is a string. That string is called happy if it does not have any of the strings like 'aaa', 'bbb' or 'ccc' as a substring. If we have three integers like a, b and c, then return any string s, which satisfies the following conditions −

• s is happy and longest possible.

• s contains at most an occurrence of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.

• s will only contain 'a', 'b' and 'c' letters.

If there is no such string, then return an empty string.

So, if the input is like a = 1, b = 1, c = 7, then the output will be "ccaccbcc"

To solve this, we will follow these steps −

• Define one data structure where character a, inx and cnt is present

• Define one priority queue pq, this will prioritize using cnt value of data

• if a is non-zero, then −

  • insert new Data('a', a, 0) into pq

• if b is non-zero, then −

  • insert new Data('b', b, 0) into pq

• if c is non-zero, then −

  • insert new Data('c', c, 0) into pq

• idx := 1

• ret := blank string

• while true is non-zero, do −

  • temp := top element of pq

  • delete element from pq

  • if size of ret is not 0 and last element of ret is same as temp.a, then −

    • if pq is empty, then −

      • Come out from the loop

    • x := temp

    • temp := top element of pq

    • delete element from pq

    • insert x into pq

  • val := 0

  • if not pq is empty and cnt of temp - cnt of first element of pq < 2, then −

    • val := 1

  • Otherwise

    • val := minimum of cnt of temp and 2

  • ret := ret concatenate val from index of temp.a in val to end

  • temp.cnt := temp.cnt - val

  • if pq is empty, then −

    • Come out from the loop

  • temp.idx := idx

  • if temp.cnt > 0, then −

    • insert temp into pq

  • (increase idx by 1)

• return ret

Example 

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; struct Data{    char a;    int cnt;    int idx ;    Data(char c, int x, int k){       a = c;       cnt = x;       idx = k;    } }; struct Cmp{    bool operator()(Data& a, Data& b) {       return !(a.cnt>b.cnt);    } }; class Solution { public:    string longestDiverseString(int a, int b, int c) {       priority_queue<Data, vector<Data>, Cmp> pq;       if (a)          pq.push(Data('a', a, 0));       if (b)          pq.push(Data('b', b, 0));       if (c)          pq.push(Data('c', c, 0));       int idx = 1;          string ret = "";       while (true) {          Data temp = pq.top();          pq.pop();          if (ret.size() && ret.back() == temp.a) {             if (pq.empty())                break;             Data x = temp;             temp = pq.top();             pq.pop();             pq.push(x);          }          int val = 0;          if (!pq.empty() && temp.cnt - pq.top().cnt < 2) {             val = 1;          }          else             val = min(temp.cnt, 2);          ret += string(val, temp.a);          temp.cnt -= val;          if (pq.empty())             break;          temp.idx = idx;          if (temp.cnt > 0)             pq.push(temp);          idx++;       }       return ret;    } }; main(){    Solution ob;    cout << (ob.longestDiverseString(1,1,7)); }

Input

1,1,7

Output

ccbccacc