Leetcode: String Without AAA or BBB

String Without AAA or BBB



Similar Problems:


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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/string-without-aaa-or-bbb
// Basic Ideas: greedy
//   Start with |B-A| pairs of "ab", then add 'a' or 'b'
// Complexity: Time O(n), Space O(1)
func strWithout3a3b(A int, B int) string {
    res := ""
    count := 0
    if A > B {
        count = B
        offset := A-B
        for offset > 0 && count > 0 {
            res += "aab"
            offset--
            count--
        }
        for i:=0; i<offset; i++ {
            res += "a"
        }
    } else {
        count = A
        offset := B-A
        for offset > 0 && count > 0 {
            res += "bba"
            offset--
            count--
        }
        for i:=0; i<offset; i++ {
            res += "b"
        }
    }
    for i:=0; i<count; i++ {
        if A > B {
            res += "ab"  
        } else {
            res += "ba"
        }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.