Sponsored
Sponsored
This approach utilizes a max heap (or priority queue) to always try to append the character with the highest remaining count without breaking the "happy" condition. Here’s the detailed plan:
Once you process all characters when the heap is non-empty, the constructed string is your answer.
Time Complexity: O(n log k), where n is the total number of characters (sum of a, b, c) and k is the number of non-zero count characters (at most 3).
Space Complexity: O(1), as we are only storing a fixed number of elements in the heap (at most 3 with their counts).
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public string LongestDiverseString(int a, int b, int c) {
6 PriorityQueue<(int count, char ch)> queue = new PriorityQueue<(int, char)>(Comparer<(int, char)>.Create((x, y) => y.count.CompareTo(x.count)));
7 if (a > 0) queue.Enqueue((a, 'a'));
8 if (b > 0) queue.Enqueue((b, 'b'));
9 if (c > 0) queue.Enqueue((c, 'c'));
10
11 var result = new System.Text.StringBuilder();
12 while (queue.Count > 0) {
13 var (count1, char1) = queue.Dequeue();
if (result.Length >= 2 && result[^1] == char1 && result[^2] == char1) {
if (queue.Count == 0) break;
var (count2, char2) = queue.Dequeue();
result.Append(char2);
if (--count2 > 0) queue.Enqueue((count2, char2));
queue.Enqueue((count1, char1));
} else {
result.Append(char1);
if (--count1 > 0) queue.Enqueue((count1, char1));
}
}
return result.ToString();
}
}The C# approach adopts a PriorityQueue for orderly character selection, considering constraints on consecutive similar characters, thus offering robust, systematic string extension without breaking the 'happy' rules.
This strategy incorporates the concepts of simulated annealing where the decision of which character to append is softly randomized, guided by the need to form a balanced happy string using all the available characters maximally — performing a structured simulation of building the string dynamically and reevaluating choices iteratively.
Time Complexity: O(k! * n), where k = 3 (permutations of distinct characters) and n denotes total character appearances.
Space Complexity: O(1), only a few data structures to hold options.
1#include <string>
2#include <tuple>
3
4std::string generateHappyString(int a, int b, int c, const std::string& pattern) {
std::string result;
int counts[3] = {a, b, c};
char chars[3] = {'a', 'b', 'c'};
for (char pat : pattern) {
auto [count, idx] = std::make_tuple(0, -1);
if (result.size() >= 2 && result.back() == pat && result[result.size() - 2] == pat) {
for (int i = 0; i < 3; ++i) {
if (counts[i] > count && chars[i] != pat) {
count = counts[i];
idx = i;
}
}
if (idx == -1) return result;
result += chars[idx];
counts[idx]--;
} else {
for (int i = 0; i < 3; ++i) {
if (counts[i] > count && chars[i] == pat) {
count = counts[i];
idx = i;
}
}
if (idx != -1) {
result += pat;
counts[idx]--;
}
}
}
return result;
}
std::string simulatedAnnealingLongestHappyString(int a, int b, int c) {
std::string patterns[6] = {"abc", "acb", "bac", "bca", "cab", "cba"};
std::string best;
for (const auto& pattern : patterns) {
std::string candidate = generateHappyString(a, b, c, pattern);
if (candidate.size() > best.size()) {
best = candidate;
}
}
return best;
}The C++ code builds potential "happy" strings by iterating through all possible orders of appending triplet combinations. For each order (swapping item positions within "abc"), potential outcomes are evaluated with respect to happy constraints and count tracking. The code iteratively improves upon choices to achieve maximal string formations.