aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-15 18:41:02 -0600
committerJack Sangdahl <[email protected]>2024-10-15 18:41:02 -0600
commitdb65a01a1b0886a72d43d0ac195effea73564425 (patch)
treecccb6118bdc8bf9bdadef67e3f88f18e4a975cd0
parenta87bcf84ff07578e6134d4e7da11b5f7d76b1c18 (diff)
downloadleetcode-db65a01a1b0886a72d43d0ac195effea73564425.tar.gz
leetcode-db65a01a1b0886a72d43d0ac195effea73564425.zip
1405. longest happy string
-rw-r--r--longest_happy_string.cpp33
-rw-r--r--longest_happy_string.py47
2 files changed, 80 insertions, 0 deletions
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))