984. String Without AAA or BBB #

Problem #

Given two integers A and B, return any string S such that:

S has length A + B and contains exactly A 'a' letters, and exactly B 'b'letters;
The substring 'aaa' does not occur in S;
The substring 'bbb' does not occur in S.

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 given A and B.

Problem Summary #

Given two integers A and B, return any string S that satisfies the following requirements:

The length of S is A + B, and it contains exactly A ‘a’ letters and B ‘b’ letters;
The substring ‘aaa’ does not appear in S;
The substring ‘bbb’ does not appear in S.

Note:

0 <= A <= 100
0 <= B <= 100
For the given A and B, it is guaranteed that an S satisfying the requirements exists.

Solution Ideas #

Given the counts of A and B, we need to combine them into a string where 3 consecutive A’s and 3 consecutive B’s must not appear. Since there are only 4 possible cases for this problem, brute-force enumeration is enough. Suppose the count of B is greater than that of A (if A is greater, swap A and B). The final possible case can only be one of these 4 cases: ba, bbabb, bbabbabb, bbabbabbabbabababa.

Code #


package leetcode

func strWithout3a3b(A int, B int) string {
	ans, a, b := "", "a", "b"
	if B < A {
		A, B = B, A
		a, b = b, a
	}
	Dif := B - A
	if A == 1 && B == 1 { // ba
		ans = b + a
	} else if A == 1 && B < 5 { // bbabb
		for i := 0; i < B-2; i++ {
			ans = ans + b
		}
		ans = b + b + a + ans
	} else if (B-A)/A >= 1 { //bbabbabb
		for i := 0; i < A; i++ {
			ans = ans + b + b + a
			B = B - 2
		}
		for i := 0; i < B; i++ {
			ans = ans + b
		}
	} else { //bbabbabbabbabababa
		for i := 0; i < Dif; i++ {
			ans = ans + b + b + a
			B -= 2
			A--
		}
		for i := 0; i < B; i++ {
			ans = ans + b + a
		}
	}
	return ans
}