984.string-without-aaa-or-bbb.md

984. String Without AAA or BBB

Greedy

We assume a >= b and it guarantees the answer exists (from problem description), we can build ab ab ab ab ... to avoid aaa or bbb, then insert the rest of a in each pair of ab:

a, b, a, b, a, b, ...

a, _, b, a, _, b, ...
   ^        ^
   a        a

Based on the idea above, we can build the string in each iteration:

• If a > b or b > a: build aab or bba. We must limit consecutive a or b to 2.
• If a == b: build ab.

At the end, we append the rest of a or b to the string.

Idea!! Always place the more frequent character first but never exceed two consecutive.

a > b，先使用 a，直到 a == b 在交錯使用 a, b

fun strWithout3a3b(A: Int, B: Int): String {
	var a = A
	var b = B
	val str = StringBuilder()
	while (a > 0 && b > 0) {
		if (a > b) {
			str.append("aab")
			a -= 2
			b -= 1
		} else if (b > a) {
			str.append("bba")
			b -= 2
			a -= 1
		} else {
			str.append("ab")
			a--
			b--
		}
	}
	if (a > 0) str.append("a".repeat(a))
	if (b > 0) str.append("b".repeat(b))
	return str.toString()
}

// Or equivalently, we can build in recursive way with the same idea.
fun strWithout3a3b(a: Int, b: Int): String {
	if (a == 0) return "b".repeat(b)
	if (b == 0) return "a".repeat(a)

	if (a > b) return "aab" + strWithout3a3b(a - 2, b - 1)
	else if (b > a) return "bba" + strWithout3a3b(a - 1, b - 2)
	else return "ab" + strWithout3a3b(a - 1, b - 1)
}

• Time Complexity: O(a + b).
• Space Complexity: O(1).

Heap

We can also use a heap to implement the same idea:

We need a way to get the maximum count and know its corresponding character ('a' or 'b'), so we use an integer array to store the count of 'a' and 'b', and a max heap to get the maximum count of 'a' or 'b'.

我們前一輪 a > b 產生 aab，接下來會不會出現 aab | bba? 答案是不會，第一輪 a > b 假設 ab 差距最小的可能是差 1，例如 a = 4, b = 3，下一輪頂多 a == b == 2，不會出現 b > a 的情況。如果 ab 差距更大，那更不可能出現下一輪減 2 減 1 後 b > a 的情況。

(4,3) -> (2,2) -> (1,1) -> (0,0): aababab
(4,2) -> (2,1) -> (0,0): aabaab
(4,1) -> (2,0): aabaa
(3,2) -> (1,1) -> (0,0): aabab
(3,1) -> (1,0) -> (0,0): aaba
(2,1) -> (0,0): aab
(2,0) -> (0,0): aa
(1,1) -> (0,0): ab

fun strWithout3a3b(a: Int, b: Int): String {
	val count = intArrayOf(a, b)
	val maxHeap = PriorityQueue<Int>() { i1, i2 ->
		count[i2] - count[i1]
	}
	(0..1).forEach { i ->
		if (count[i] > 0) maxHeap.add(i)
	}
	val str = StringBuilder()
	while (maxHeap.size >= 2) {
		val i1 = maxHeap.poll()
		val i2 = maxHeap.poll()
		val char1 = 'a' + i1
		var char2 = 'a' + i2
		if (count[i1] > count[i2]) {
			str.append("$char1$char1$char2")
			count[i1] -= 2
			count[i2] -= 1
		} else {
			str.append("$char1$char2")
			count[i1] -= 1
			count[i2] -= 1
		}
		if (count[i1] > 0) maxHeap.add(i1)
		if (count[i2] > 0) maxHeap.add(i2)
	}
	if (maxHeap.isNotEmpty()) {
		val i = maxHeap.poll()
		val c = 'a' + i
		// Here we don't need to check if count > 2, tt is guaranteed 
		// such an s exists for the given a and b. (from problem description)
		val count = count[i]
		str.append(c.toString().repeat(count))
	}
	return str.toString()
}

• Time Complexity: O(n log n), where n is the sum of a and b.
• Space Complexity: O(n).