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, and
  • The substring 'bbb' does not occur in s.

Examples

Example 1

1
2
3

Input: a = 1, b = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

Example 2

1
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.

Solution

Method 1 - Greedy Construction

Intuition

To avoid three consecutive ‘a’s or ‘b’s, always append the character with the larger remaining count, but never more than two in a row. If two of the same character are already at the end, append the other character.

Approach

Use a greedy loop: at each step, check the last two characters. If the last two are not the same, append the character with more left. If the last two are the same, append the other character. Repeat until both counts are zero.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <string>
using namespace std;
class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string res = "";
        while (a > 0 || b > 0) {
            if ((a > b && a > 0) || (res.size() >= 2 && res.back() == 'b' && res[res.size()-2] == 'b')) {
                if (a > 0) { res += 'a'; --a; }
                else { res += 'b'; --b; }
            } else {
                if (b > 0) { res += 'b'; --b; }
                else { res += 'a'; --a; }
            }
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func strWithout3a3b(a int, b int) string {
    res := []byte{}
    for a > 0 || b > 0 {
        n := len(res)
        if (a > b && a > 0) || (n >= 2 && res[n-1] == 'b' && res[n-2] == 'b') {
            if a > 0 {
                res = append(res, 'a')
                a--
            } else {
                res = append(res, 'b')
                b--
            }
        } else {
            if b > 0 {
                res = append(res, 'b')
                b--
            } else {
                res = append(res, 'a')
                a--
            }
        }
    }
    return string(res)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder res = new StringBuilder();
        while (a > 0 || b > 0) {
            int n = res.length();
            if ((a > b && a > 0) || (n >= 2 && res.charAt(n-1) == 'b' && res.charAt(n-2) == 'b')) {
                if (a > 0) { res.append('a'); a--; }
                else { res.append('b'); b--; }
            } else {
                if (b > 0) { res.append('b'); b--; }
                else { res.append('a'); a--; }
            }
        }
        return res.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

fun strWithout3a3b(a: Int, b: Int): String {
    val res = StringBuilder()
    var a = a; var b = b
    while (a > 0 || b > 0) {
        val n = res.length
        if ((a > b && a > 0) || (n >= 2 && res[n-1] == 'b' && res[n-2] == 'b')) {
            if (a > 0) { res.append('a'); a-- }
            else { res.append('b'); b-- }
        } else {
            if (b > 0) { res.append('b'); b-- }
            else { res.append('a'); a-- }
        }
    }
    return res.toString()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def strWithout3a3b(a: int, b: int) -> str:
    res = []
    while a > 0 or b > 0:
        n = len(res)
        if (a > b and a > 0) or (n >= 2 and res[-1] == 'b' and res[-2] == 'b'):
            if a > 0:
                res.append('a')
                a -= 1
            else:
                res.append('b')
                b -= 1
        else:
            if b > 0:
                res.append('b')
                b -= 1
            else:
                res.append('a')
                a -= 1
    return ''.join(res)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

pub fn str_without_3a3b(mut a: i32, mut b: i32) -> String {
    let mut res = Vec::new();
    while a > 0 || b > 0 {
        let n = res.len();
        if (a > b && a > 0) || (n >= 2 && res[n-1] == b'b' && res[n-2] == b'b') {
            if a > 0 {
                res.push(b'a'); a -= 1;
            } else {
                res.push(b'b'); b -= 1;
            }
        } else {
            if b > 0 {
                res.push(b'b'); b -= 1;
            } else {
                res.push(b'a'); a -= 1;
            }
        }
    }
    String::from_utf8(res).unwrap()
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function strWithout3a3b(a: number, b: number): string {
    const res: string[] = [];
    while (a > 0 || b > 0) {
        const n = res.length;
        if ((a > b && a > 0) || (n >= 2 && res[n-1] === 'b' && res[n-2] === 'b')) {
            if (a > 0) { res.push('a'); a--; }
            else { res.push('b'); b--; }
        } else {
            if (b > 0) { res.push('b'); b--; }
            else { res.push('a'); a--; }
        }
    }
    return res.join("");
}

Complexity

  • ⏰ Time complexity: O(a + b)
  • 🧺 Space complexity: O(a + b)