DDSA Solutions

1405. Longest Happy String

UnknownView on LeetCode
StringGreedyHeap (Priority Queue)
Time: O(a+b+c)
Space: O(a+b+c)

Problem Overview

Greedily append the most frequent character that isn't the same as last two appended.

Intuition

Greedily append the most frequent character that isn't the same as last two appended. Use a max-heap.

Algorithm

  1. 1Max-heap of (freq, char).
  2. 2Each step: pop max. If same as last two chars, pop second-max, use it, push max back.
  3. 3Append character, decrement frequency, push back if freq > 0.

Common Pitfalls

  • •Same approach as task scheduler problem. Track the last character added to avoid consecutive triples.
1405.cs
C#
// Approach: Greedy recursive; always use up to 2 of the most-frequent character, then 1 of the second most.
// Time: O(a+b+c) Space: O(a+b+c)

public class Solution
{
    public string LongestDiverseString(int a, int b, int c, char A = 'a', char B = 'b', char C = 'c')
    {
        if (a < b)
            return LongestDiverseString(b, a, c, B, A, C);
        if (b < c)
            return LongestDiverseString(a, c, b, A, C, B);
        if (b == 0)
            return new string(A, Math.Min(a, 2));

        int useA = Math.Min(a, 2);
        int useB = (a - useA >= b) ? 1 : 0;
        return new string(A, useA) + new string(B, useB) +
               LongestDiverseString(a - useA, b - useB, c, A, B, C);
    }
}
Was this solution helpful?

Related Problems