0984. String Without a a a or B B B

984. String Without AAA or BBB #

题目 #

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:

  1. 0 <= A <= 100
  2. 0 <= B <= 100
  3. It is guaranteed such an S exists for the given A and B.

题目大意 #

给定两个整数 A 和 B,返回任意字符串 S,要求满足:

  • S 的长度为 A + B,且正好包含 A 个 ‘a’ 字母与 B 个 ‘b’ 字母;
  • 子串 ‘aaa’ 没有出现在 S 中;
  • 子串 ‘bbb’ 没有出现在 S 中。

提示:

  • 0 <= A <= 100
  • 0 <= B <= 100
  • 对于给定的 A 和 B,保证存在满足要求的 S。

解题思路 #

  • 给出 A 和 B 的个数,要求组合出字符串,不能出现 3 个连续的 A 和 3 个连续的 B。这题由于只可能有 4 种情况,暴力枚举就可以了。假设 B 的个数比 A 多(如果 A 多,就交换一下 A 和 B),最终可能的情况只可能是这 4 种情况中的一种: babbabbbbabbabbbbabbabbabbabababa

代码 #


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
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者