Longest Happy String

NeetCode: Longest Happy String · LeetCode: 1405. Longest Happy String · Difficulty: Medium

A string is happy if it uses only the letters a, b, c, contains no aaa, bbb or ccc as a substring, and uses at most a copies of a, at most b copies of b, and at most c copies of c. Given a, b, c, return the longest happy string. If several are longest, any is accepted.

Example

Text

Input:  a = 1, b = 1, c = 7   Output: "ccaccbcc"
Input:  a = 7, b = 1, c = 0   Output: "aabaa"

To make the output deterministic, both programs below break ties between equal counts by preferring the alphabetically smaller letter.

Better: greedy, re-sort the three counts each step

The method name is longestDiverseString, as on LeetCode. An int[] entry holds {copies left, letter}; a char such as 'a' widens to its int code inside an int[] initializer, and (char) converts it back.

Greedy idea: at each step, append the letter with the most copies left, unless that would make three in a row. In that case use the second most plentiful letter instead. If that one is exhausted too, stop. Spending the largest pile first leaves the other letters available to separate it.

Because there are only three letters, "find the largest" is a sort of three items, which is O(1).

Java

import java.util.Arrays;

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        int[][] left = {{a, 'a'}, {b, 'b'}, {c, 'c'}}; // {copies left, letter}
        StringBuilder out = new StringBuilder();
        while (true) {
            // most copies first, alphabetical on ties
            Arrays.sort(left, (x, y) -> x[0] != y[0] ? Integer.compare(y[0], x[0]) : Integer.compare(x[1], y[1]));
            boolean placed = false;
            for (int k = 0; k < 3; k++) {
                int count = left[k][0];
                char ch = (char) left[k][1];
                if (count == 0) {
                    break;
                }
                int n = out.length();
                if (n >= 2 && out.charAt(n - 1) == ch && out.charAt(n - 2) == ch) {
                    continue;
                }
                out.append(ch);
                left[k][0]--;
                placed = true;
                break;
            }
            if (!placed) {
                break;
            }
        }
        return out.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestDiverseString(1, 1, 7));
        System.out.println(s.longestDiverseString(7, 1, 0));
        System.out.println(s.longestDiverseString(0, 0, 0));
        System.out.println(s.longestDiverseString(2, 2, 2));
    }
}

Output

ccaccbcc
aabaa

abcabc

Each step sorts 3 elements and the loop runs once per output character. Time: O(a + b + c). Space: O(a + b + c) for the output.

Optimal: the same greedy with a max-heap

The same greedy with a heap works for any alphabet size: poll the letter with the most copies; if it would make three in a row, poll the next one instead, place that, and add both back. The comparator orders by copies descending, then letter ascending. It uses Integer.compare, not a subtraction. With three letters the heap holds at most 3 entries, so both versions are linear in the output length; the heap version scales to k letters at O(n log k).

Java

import java.util.PriorityQueue;

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        // Entry: {copies left, letter}. Most copies first; on ties the alphabetically smaller letter wins.
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (x, y) -> x[0] != y[0] ? Integer.compare(y[0], x[0]) : Integer.compare(x[1], y[1]));
        if (a > 0) heap.add(new int[]{a, 'a'});
        if (b > 0) heap.add(new int[]{b, 'b'});
        if (c > 0) heap.add(new int[]{c, 'c'});
        StringBuilder out = new StringBuilder();
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            char ch = (char) top[1];
            int n = out.length();
            if (n >= 2 && out.charAt(n - 1) == ch && out.charAt(n - 2) == ch) {
                // ch is blocked, so use the next best letter once
                if (heap.isEmpty()) {
                    break;
                }
                int[] second = heap.poll();
                out.append((char) second[1]);
                if (second[0] > 1) {
                    heap.add(new int[]{second[0] - 1, second[1]});
                }
                heap.add(top);
            } else {
                out.append(ch);
                if (top[0] > 1) {
                    heap.add(new int[]{top[0] - 1, top[1]});
                }
            }
        }
        return out.toString();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestDiverseString(1, 1, 7));
        System.out.println(s.longestDiverseString(7, 1, 0));
        System.out.println(s.longestDiverseString(0, 0, 0));
        System.out.println(s.longestDiverseString(2, 2, 2));
    }
}

Output

ccaccbcc
aabaa

abcabc

Time: O(n log k) with k = 3 letters, so O(a + b + c). Space: O(a + b + c) for the output.