Skip to main content

1405. Longest Happy String

medium

Build the longest string from up to three character budgets without ever repeating any letter three times in a row. A direct cousin of reorganize-string — a max-heap plus a lookahead rule.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

Input
a = 1, b = 1, c = 7
Output
"ccaccbcc"

Explanation: 'ccbccacc' would also be a valid answer.

Example 2

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

Explanation: It is the only correct answer in this case.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Greedy: always append the letter with the largest remaining budget.

Hint 2

Exception: if the last two characters of the result are already that letter, you'd hit the 'aaa' rule. Pick the next-largest instead.

Hint 3

A max-heap of (count, letter) pairs makes 'pick the largest remaining' an O(log 3) op.

Hint 4

After appending the second-largest, push the largest back into the heap and continue. Stop when the heap is empty or you can't legally append.

Solution approach

Reveal approach

Max-heap of (-count, letter) pairs (Python's heapq is a min-heap, so negate). Loop: pop the top letter. If the result's last two chars equal this letter, pop the next one instead — if the heap is now empty, return the result (we can't legally continue). Append the chosen letter, decrement its count, push it back if count > 0. Also remember to push the temporarily-skipped letter back. Continue until termination. Each step is O(log 3) = O(1), so total O(a+b+c). The trick is the two-char lookahead — you never need to look further back because once you append a letter, future runs of it are reset by whatever you appended in between.

Complexity

Time
O(a + b + c)
Space
O(1)

Related patterns

  • heap
  • greedy
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Longest Happy String and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →