Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/984.html
984. String Without AAA or BBB (Medium)
Given two integers A
and B
, return any string S
such that:
S
has lengthA + B
and contains exactlyA
'a'
letters, and exactlyB
'b'
letters;- The substring
'aaa'
does not occur inS
; - The substring
'bbb'
does not occur inS
.
Example 1:
Input: A = 1, B = 2 Output: "abb" Explanation: "abb", "bab" and "bba" are all correct answers.
Example 2:
Input: A = 4, B = 1 Output: "aabaa"
Note:
0 <= A <= 100
0 <= B <= 100
- It is guaranteed such an
S
exists for the givenA
andB
.
Related Topics:
Greedy
Solution 1.
-
class Solution { public String strWithout3a3b(int A, int B) { StringBuffer sb = new StringBuffer(); while (A > B && B > 0) { sb.append("aab"); A -= 2; B--; } while (A < B && A > 0) { sb.append("bba"); B -= 2; A--; } while (A > 0 && B > 0) { sb.append("ab"); A--; B--; } while (A > 0) { sb.append("a"); A--; } while (B > 0) { sb.append("b"); B--; } return sb.toString(); } } ############ class Solution { public String strWithout3a3b(int a, int b) { StringBuilder ans = new StringBuilder(); while (a > 0 && b > 0) { if (a > b) { ans.append("aab"); a -= 2; b -= 1; } else if (a < b) { ans.append("bba"); a -= 1; b -= 2; } else { ans.append("ab"); --a; --b; } } if (a > 0) { ans.append("a".repeat(a)); } if (b > 0) { ans.append("b".repeat(b)); } return ans.toString(); } }
-
// OJ: https://leetcode.com/problems/string-without-aaa-or-bbb/ // Time: O(A + B) // Space: O(1) class Solution { public: string strWithout3a3b(int A, int B) { char a = 'a', b = 'b'; if (A < B) swap(A, B), swap(a, b); string ans; while (A && B) { for (int i = A > B ? 2 : 1; i > 0; --i, --A) ans += a; ans += b; --B; } while (A-- > 0) ans += a; return ans; } };
-
class Solution: def strWithout3a3b(self, a: int, b: int) -> str: ans = [] while a and b: if a > b: ans.append('aab') a, b = a - 2, b - 1 elif a < b: ans.append('bba') a, b = a - 1, b - 2 else: ans.append('ab') a, b = a - 1, b - 1 if a: ans.append('a' * a) if b: ans.append('b' * b) return ''.join(ans) ############ class Solution(object): def strWithout3a3b(self, A, B): """ :type A: int :type B: int :rtype: str """ _len = A + B # to make A > B a, b = ('a', 'b') if A > B else ('b', 'a') A, B = (A, B) if A > B else (B, A) ab = [a + b] * B A -= B res = [] while A: res.append(a) if ab: res.append(ab.pop()) A -= 1 res += ab return "".join(res)
-
func strWithout3a3b(a int, b int) string { var ans strings.Builder for a > 0 && b > 0 { if a > b { ans.WriteString("aab") a -= 2 b -= 1 } else if a < b { ans.WriteString("bba") a -= 1 b -= 2 } else { ans.WriteString("ab") a-- b-- } } if a > 0 { ans.WriteString(strings.Repeat("a", a)) } if b > 0 { ans.WriteString(strings.Repeat("b", b)) } return ans.String() }