Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

984. String Without AAA or BBB - Leetcode Solution

Code Implementation

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        res = []
        while a > 0 or b > 0:
            if a > b:
                if a >= 2:
                    res.append('aa')
                    a -= 2
                else:
                    res.append('a')
                    a -= 1
                if b > 0:
                    res.append('b')
                    b -= 1
            elif b > a:
                if b >= 2:
                    res.append('bb')
                    b -= 2
                else:
                    res.append('b')
                    b -= 1
                if a > 0:
                    res.append('a')
                    a -= 1
            else:
                if a > 0:
                    res.append('a')
                    a -= 1
                if b > 0:
                    res.append('b')
                    b -= 1
        return ''.join(res)
      
class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string res = "";
        while (a > 0 || b > 0) {
            if (a > b) {
                if (a >= 2) {
                    res += "aa";
                    a -= 2;
                } else {
                    res += "a";
                    a -= 1;
                }
                if (b > 0) {
                    res += "b";
                    b -= 1;
                }
            } else if (b > a) {
                if (b >= 2) {
                    res += "bb";
                    b -= 2;
                } else {
                    res += "b";
                    b -= 1;
                }
                if (a > 0) {
                    res += "a";
                    a -= 1;
                }
            } else {
                if (a > 0) {
                    res += "a";
                    a -= 1;
                }
                if (b > 0) {
                    res += "b";
                    b -= 1;
                }
            }
        }
        return res;
    }
};
      
class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder res = new StringBuilder();
        while (a > 0 || b > 0) {
            if (a > b) {
                if (a >= 2) {
                    res.append("aa");
                    a -= 2;
                } else {
                    res.append("a");
                    a -= 1;
                }
                if (b > 0) {
                    res.append("b");
                    b -= 1;
                }
            } else if (b > a) {
                if (b >= 2) {
                    res.append("bb");
                    b -= 2;
                } else {
                    res.append("b");
                    b -= 1;
                }
                if (a > 0) {
                    res.append("a");
                    a -= 1;
                }
            } else {
                if (a > 0) {
                    res.append("a");
                    a -= 1;
                }
                if (b > 0) {
                    res.append("b");
                    b -= 1;
                }
            }
        }
        return res.toString();
    }
}
      
var strWithout3a3b = function(a, b) {
    let res = [];
    while (a > 0 || b > 0) {
        if (a > b) {
            if (a >= 2) {
                res.push('aa');
                a -= 2;
            } else {
                res.push('a');
                a -= 1;
            }
            if (b > 0) {
                res.push('b');
                b -= 1;
            }
        } else if (b > a) {
            if (b >= 2) {
                res.push('bb');
                b -= 2;
            } else {
                res.push('b');
                b -= 1;
            }
            if (a > 0) {
                res.push('a');
                a -= 1;
            }
        } else {
            if (a > 0) {
                res.push('a');
                a -= 1;
            }
            if (b > 0) {
                res.push('b');
                b -= 1;
            }
        }
    }
    return res.join('');
};

Problem Description

You are given two integers, a and b, representing the number of letters 'a' and 'b' you must use to construct a string. The task is to create any string using exactly a 'a's and b 'b's such that the string does not contain the substring 'aaa' or 'bbb' anywhere. In other words, you cannot have three consecutive 'a's or three consecutive 'b's in your result. Any valid solution is accepted, and you do not have to generate all possibilities—just one valid string that satisfies the constraints.

Thought Process

When first approaching this problem, you might consider brute-forcing all possible permutations of 'a' and 'b' and filtering out those with three consecutive identical letters. However, this quickly becomes infeasible as the numbers get larger due to the exponential number of permutations. Instead, it's more efficient to build the string step by step, always making sure that you never add a third consecutive 'a' or 'b'. At each step, you want to add the letter that is most plentiful, unless doing so would create an invalid sequence. This greedy approach ensures you use up your letters while always maintaining the rules.

Solution Approach

The solution uses a greedy algorithm to construct the string. Here’s how it works, step by step:
  • Track the counts: Start with the given numbers of 'a' and 'b'.
  • Build incrementally: At each step, decide which letter to add next based on which one has more remaining, but never allow three of the same letter in a row.
  • Preventing triples: If adding a letter would create three consecutive of that letter, you must add the other letter instead (if available).
  • Greedy choice: When possible, add two of the letter that has more left, then one of the other. This helps balance the counts and avoids getting stuck.
  • Continue until done: Repeat the process until both counts reach zero.
This approach ensures that you always make a safe move and never create an invalid substring, while also using up all your letters efficiently.

Example Walkthrough

Let's take a = 4 and b = 2 as an example.
  • Start: a = 4, b = 2, result = ""
  • a > b, so add "aa" (now a = 2, b = 2, result = "aa")
  • Now, add "b" (a = 2, b = 1, result = "aab")
  • a > b again, so add "aa" (a = 0, b = 1, result = "aabaa")
  • Finally, add "b" (a = 0, b = 0, result = "aabaab")
At each step, we make sure not to add a third 'a' or 'b' in a row. The final string "aabaab" contains exactly 4 'a's and 2 'b's, and has no "aaa" or "bbb" substrings.

Time and Space Complexity

  • Brute-force approach: Generating all permutations would take O((a+b)!) time and space, which is infeasible for large inputs.
  • Optimized greedy approach: We only loop up to a+b times, once for each letter added, so the time complexity is O(a+b). The space complexity is also O(a+b), since we store the result string of that length.
The greedy approach is efficient and works well even for large values of a and b.

Summary

This problem is a classic example of using a greedy strategy to build a string under specific constraints. By always choosing the most plentiful letter—unless it would create three in a row—we efficiently construct a valid string without "aaa" or "bbb". The solution is elegant because it doesn't backtrack or brute-force, but always makes a safe, optimal choice at each step, ensuring correctness and efficiency.