1405 - Longest Happy String

A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

 Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

 Constraints:

• 0 <= a, b, c <= 100
• a + b + c > 0

C++

• class Solution {
  public:
      string longestDiverseString(int a, int b, int c) {
          using pci = pair<char, int>;
          auto cmp = [](pci x, pci y) { return x.second < y.second; };
          priority_queue<pci, vector<pci>, decltype(cmp)> pq(cmp);
  
          if (a > 0) pq.push({'a', a});
          if (b > 0) pq.push({'b', b});
          if (c > 0) pq.push({'c', c});
  
          string ans;
          while (!pq.empty()) {
              pci cur = pq.top();
              pq.pop();
              int n = ans.size();
              if (n >= 2 && ans[n - 1] == cur.first && ans[n - 2] == cur.first) {
                  if (pq.empty()) break;
                  pci nxt = pq.top();
                  pq.pop();
                  ans.push_back(nxt.first);
                  if (--nxt.second > 0) {
                      pq.push(nxt);
                  }
                  pq.push(cur);
              } else {
                  ans.push_back(cur.first);
                  if (--cur.second > 0) {
                      pq.push(cur);
                  }
              }
          }
  
          return ans;
      }
  };

PYTHON

• import heapq
  
  class Solution:
      def longestDiverseString(self, a: int, b: int, c: int) -> str:
          pq = []
          if a > 0:
              heapq.heappush(pq, (-a, 'a'))
          if b > 0:
              heapq.heappush(pq, (-b, 'b'))
          if c > 0:
              heapq.heappush(pq, (-c, 'c'))
  
          ans = []
          
          while pq:
              count, char = heapq.heappop(pq)
              count = -count
              n = len(ans)
              if n >= 2 and ans[-1] == char and ans[-2] == char:
                  if not pq:
                      break
                  next_count, next_char = heapq.heappop(pq)
                  next_count = -next_count
                  ans.append(next_char)
                  next_count -= 1
                  
                  if next_count > 0:
                      heapq.heappush(pq, (-next_count, next_char))
                  
                  heapq.heappush(pq, (-count, char))
              else:
                  ans.append(char)
                  count -= 1
                  
                  if count > 0:
                      heapq.heappush(pq, (-count, char))
          
          return ''.join(ans)

JAVA

• class Solution {
      public String longestDiverseString(int a, int b, int c) {
          Queue<int[]> pq = new PriorityQueue<>((x, y) -> y[1] - x[1]);
          if (a > 0) {
              pq.offer(new int[] {'a', a});
          }
          if (b > 0) {
              pq.offer(new int[] {'b', b});
          }
          if (c > 0) {
              pq.offer(new int[] {'c', c});
          }
  
          StringBuilder sb = new StringBuilder();
          while (pq.size() > 0) {
              int[] cur = pq.poll();
              int n = sb.length();
              if (n >= 2 && sb.codePointAt(n - 1) == cur[0] && sb.codePointAt(n - 2) == cur[0]) {
                  if (pq.size() == 0) {
                      break;
                  }
                  int[] next = pq.poll();
                  sb.append((char) next[0]);
                  if (next[1] > 1) {
                      next[1]--;
                      pq.offer(next);
                  }
                  pq.offer(cur);
              } else {
                  sb.append((char) cur[0]);
                  if (cur[1] > 1) {
                      cur[1]--;
                      pq.offer(cur);
                  }
              }
          }
  
          return sb.toString();
      }
  }