Longest Happy String

medium string greedy heap

Problem

Given counts a, b, c of letters 'a','b','c', build the longest string with no three consecutive identical letters. Return any valid answer.

Inputa = 1, b = 1, c = 7

Output"ccaccbcc"

Greedily use the most-remaining 'c', breaking up with 'a' or 'b' as needed.

import heapq
def longest_diverse_string(a, b, c):
    h = []
    for cnt, ch in [(-a, 'a'), (-b, 'b'), (-c, 'c')]:
        if cnt: heapq.heappush(h, (cnt, ch))
    out = []
    while h:
        cnt, ch = heapq.heappop(h)
        if len(out) >= 2 and out[-1] == out[-2] == ch:
            if not h: break
            cnt2, ch2 = heapq.heappop(h)
            out.append(ch2)
            if cnt2 + 1: heapq.heappush(h, (cnt2 + 1, ch2))
            heapq.heappush(h, (cnt, ch))
        else:
            out.append(ch)
            if cnt + 1: heapq.heappush(h, (cnt + 1, ch))
    return ''.join(out)

function longestDiverseString(a, b, c) {
  const heap = [];
  function push(cnt, ch) { if (cnt > 0) heap.push([cnt, ch]); heap.sort((x, y) => y[0] - x[0]); }
  push(a, 'a'); push(b, 'b'); push(c, 'c');
  const out = [];
  while (heap.length) {
    const [cnt, ch] = heap.shift();
    if (out.length >= 2 && out[out.length - 1] === ch && out[out.length - 2] === ch) {
      if (!heap.length) break;
      const [cnt2, ch2] = heap.shift();
      out.push(ch2); push(cnt2 - 1, ch2); push(cnt, ch);
    } else { out.push(ch); push(cnt - 1, ch); }
  }
  return out.join('');
}

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue pq = new PriorityQueue<>((x, y) -> y[0] - x[0]);
        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.isEmpty()) {
            int[] x = pq.poll();
            int L = sb.length();
            if (L >= 2 && sb.charAt(L-1) == x[1] && sb.charAt(L-2) == x[1]) {
                if (pq.isEmpty()) break;
                int[] y = pq.poll();
                sb.append((char) y[1]);
                if (--y[0] > 0) pq.offer(y);
                pq.offer(x);
            } else { sb.append((char) x[1]); if (--x[0] > 0) pq.offer(x); }
        }
        return sb.toString();
    }
}

string longestDiverseString(int a, int b, int c) {
    priority_queue> pq;
    if (a) pq.push({a, 'a'}); if (b) pq.push({b, 'b'}); if (c) pq.push({c, 'c'});
    string s;
    while (!pq.empty()) {
        auto [cnt, ch] = pq.top(); pq.pop();
        int L = s.size();
        if (L >= 2 && s[L-1] == ch && s[L-2] == ch) {
            if (pq.empty()) break;
            auto [c2, ch2] = pq.top(); pq.pop();
            s.push_back(ch2); if (--c2) pq.push({c2, ch2});
            pq.push({cnt, ch});
        } else { s.push_back(ch); if (--cnt) pq.push({cnt, ch}); }
    }
    return s;
}

Explanation

We build the string one letter at a time, always trying to use the letter we have the most of. A max-heap on remaining counts gives us that most-plentiful letter instantly.

The only rule is no three identical letters in a row. So before appending the top letter, we check: would it make three of the same at the end? If not, we append it and decrease its count, pushing it back if any remain.

If the top letter would create a triple, we instead take the second-most-plentiful letter, append one of it, and put the top letter back unchanged. This breaks up the run while still using a letter we have plenty of.

If we hit a triple and there is no second letter to fall back on, we stop — we cannot extend the string any further.

Example: a=1, b=1, c=7. We lay down "cc", but a third 'c' would make a triple, so we insert a different letter: "cca". Continuing greedily yields something like "ccaccbcc", which uses the 'c's as much as possible without ever tripling.

Time: O((a+b+c) log 3) Space: O(a+b+c)