Skip to content

984. String Without AAA or BBB

Description

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, and
  • 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"

 

Constraints:

  • 0 <= a, b <= 100
  • It is guaranteed such an s exists for the given a and b.

Solutions

Solution 1

Thinking

Build a string with \(a\) 'a's and \(b\) 'b's that avoids aaa/bbb. The more frequent letter should be emitted in pairs, separated by the rarer one, so it does not clump. Append aab when \(a>b\), bba when \(b>a\), ab when equal, then the leftover singles.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string ans;
        while (a && b) {
            if (a > b) {
                ans += "aab";
                a -= 2;
                b -= 1;
            } else if (a < b) {
                ans += "bba";
                a -= 1;
                b -= 2;
            } else {
                ans += "ab";
                --a;
                --b;
            }
        }
        if (a) ans += string(a, 'a');
        if (b) ans += string(b, 'b');
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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()
}

Comments