From db65a01a1b0886a72d43d0ac195effea73564425 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Tue, 15 Oct 2024 18:41:02 -0600 Subject: 1405. longest happy string --- longest_happy_string.cpp | 33 +++++++++++++++++++++++++++++++++ longest_happy_string.py | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 80 insertions(+) create mode 100644 longest_happy_string.cpp create mode 100644 longest_happy_string.py diff --git a/longest_happy_string.cpp b/longest_happy_string.cpp new file mode 100644 index 0000000..ea3ad78 --- /dev/null +++ b/longest_happy_string.cpp @@ -0,0 +1,33 @@ +// 1405. Longest Happy String +#include "leetcode.h" + +/* + * a string 's' is called happy if it satisfies the following conditions: 's' + * only contains the letters 'a', 'b', 'c', does not contain any of 'aaa', + * 'bbb', or 'ccc' as a substring, contains at most 'n' occurences of the + * letters 'a', 'b', 'c'. given three integers, 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 + */ + +class Solution { +public: + string longestDiverseString(int a, int b, int c, char aa = 'a', char bb = 'b', + char cc = 'c') { + if (a < b) + return longestDiverseString(b, a, c, bb, aa, cc); + if (b < c) + return longestDiverseString(a, c, b, aa, cc, bb); + if (!b) + return string(min(2, a), aa); + auto use_a = min(2, a), use_b = a - use_a >= b ? 1 : 0; + return string(use_a, aa) + string(use_b, bb) + + longestDiverseString(a - use_a, b - use_b, c, aa, bb, cc); + } +}; + +int main() { + Solution obj; + cout << obj.longestDiverseString(1, 1, 7) << endl; // expect: ccaccbcc + cout << obj.longestDiverseString(7, 1, 0) << endl; // expect: aabaa +} diff --git a/longest_happy_string.py b/longest_happy_string.py new file mode 100644 index 0000000..6a0ea2a --- /dev/null +++ b/longest_happy_string.py @@ -0,0 +1,47 @@ +# 1405. Longest Happy String +from collections import Counter + +""" +a string 's' is called happy if it satisfies the following conditions: 's' +only contains the letters 'a', 'b', 'c', does not contain any of 'aaa', +'bbb', or 'ccc' as a substring, contains at most 'n' occurences of the +letters 'a', 'b', 'c'. given three integers, 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 +""" + + +class Solution(object): + def longestDiverseString(self, a, b, c): + """ + :type a: int + :type b: int + :type c: int + :rtype: str + """ + ans = [] + rem = Counter({"a": a, "b": b, "c": c}) + (fence, _), (wedge, _) = rem.most_common(2) + while rem[fence] > 0 and rem[wedge] > 0: + ans.append(fence) + rem[fence] -= 1 + if len(ans) >= 2 and ans[-2] == fence: + pass + elif rem[fence] > 0: + ans.append(fence) + rem[fence] -= 1 + ans.append(wedge) + rem[wedge] -= 1 + (fence, _), (wedge, _) = rem.most_common(2) + if rem[fence] > 0: + ans.append(fence) + rem[fence] -= 1 + if rem[fence] > 0: + ans.append(fence) + return "".join(ans) + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestDiverseString(a=1, b=1, c=7)) + print(obj.longestDiverseString(a=7, b=1, c=0)) -- cgit v1.2.3