984. String Without AAA or BBB

MediumGreedyString

Problem Description

Given two integers a and b, we are asked to construct a string s of length a + b which contains exactly a 'a' letters and b 'b' letters. However, the string s must not contain the substrings 'aaa' or 'bbb', which means we are not allowed to have three consecutive 'a's or 'b's. The task is to return any such string that satisfies all the conditions.

Intuition

The core idea behind the solution is to create the string by appending letters in a pattern that prevents three consecutive identical characters from being formed. This is accomplished by deciding on the order of 'a's and 'b's to be added to the string based on their counts. If we have more 'a's than 'b's, it means we should avoid adding too many 'a's in a row to prevent forming 'aaa'. Similarly, if there are more 'b's, we should avoid adding too many 'b's in a row.

To achieve this, we use a greedy approach, where we sequentially build the final string by appending the characters in small blocks in the required sequence:

When a > b, we insert a block 'aab'. This uses up more 'a's than 'b's but keeps a safe distance from the forbidden 'aaa' sequence.
When b > a, we do the opposite, inserting a block of 'bba', using up more 'b's while avoiding the forbidden 'bbb'.
When a == b, this means we have an equal number of 'a' and 'b' left, and to maintain the balance we add 'ab' (or 'ba', both are valid) as it does not further skew the balance between 'a' and 'b'.

Once one of the counts reaches zero and the other still has characters left, we can safely append the remaining characters one by one. Since the other character's count is at zero, there is no risk of forming a forbidden sequence. The remaining 'a' or 'b' characters will either be appended at the end of the string as a series of unbroken 'a's or 'b's (but not more than two), or distributed through the already appended blocks, ensuring no forbidden sequences can form.

The join operation is used at the end to convert the list of strings into a single string as the output. Each block appended to the list ensures that the conditions are maintained, and the join simply merges them into the required output format.

Learn more about Greedy patterns.

Solution Approach

The solution to the string problem uses a greedy algorithm, which is a method for making a sequence of choices in a local optimum manner with the hope that this will lead to a global optimum. The algorithm closely follows the intuition to alternate characters in a way that avoids having three consecutive 'a's or 'b's. It uses a loop to construct the string piece by piece, appending "blocks" of characters based on the count of 'a's and 'b's remaining.

The data structure used in the implementation is primarily a list, which in Python can be efficiently appended to, and it also provides the ability to later convert it to a string with the join() method. The algorithm works as follows:

Initialize an empty list ans that will contain blocks of the final string.
Enter a while loop that continues as long as both a and b have remaining characters (i.e., a > 0 and b > 0).
Within the while loop, the following checks are made:
- If a > b, it means there are more 'a's to be placed than 'b's. So, append 'aab' to the list and decrement a by 2 and b by 1 to reflect the characters used.
- If a < b, there are more 'b's left, hence append 'bba' to the list, and decrement a by 1 and b by 2.
- If a == b, there is a balance, so append 'ab' to the list, and decrement both a and b by 1.
Once the while loop exits, it will either be because a or b is 0. If there are any 'a's left (i.e., a is not 0), append the remaining 'a's as a block to the list. Since 'b' is 0, there's no risk of forming 'aaa'.
Similarly, if there are any 'b's left, append them as a single block ('b' * b). There will be no 'a' characters left to pair with, preventing 'bbb' from forming.
Finally, the join() method is used to convert the list of strings into a single string result.

The algorithm ensures that at each step, no block that could lead to either 'aaa' or 'bbb' being formed is ever added, yielding a string that fits the constraints of the problem. There's no need to backtrack or check the entire string at any point since the construction of the string is done with local decisions that respect the global constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's say we have a = 4 and b = 3. Our goal is to construct a string of length a + b = 7 that contains exactly 4 'a's and 3 'b's without having 'aaa' or 'bbb'.

Now, let's walk through the steps:

Initialize the list ans as empty. This will hold the pieces of our final string.
Enter the while loop since both a (4) and b (3) are greater than 0.
Since a > b, we append the block 'aab' to ans, yielding ans = ['aab']. We then decrement a by 2 (now a = 2) and b by 1 (now b = 2).
Next iteration of the loop, a (2) and b (2) are now equal. We add 'ab' to ans, resulting in ans = ['aab', 'ab']. We decrement both a and b by 1, so now a = 1 and b = 1.
In the next iteration, a and b are still equal, so we add another ab. Now ans = ['aab', 'ab', 'ab'] and both a and b are decremented by 1, leaving both a = 0 and b = 0.
Since a is 0, we don't need to add any more 'a's and since b is 0 as well, we don't need to add any more 'b's. The loop ends here.
Lastly, we use the join() method on ans to get the final string. Joining ['aab', 'ab', 'ab'] we get the final string "aabbab".

The resultant string "aabbab" is of length 7, contains exactly 4 'a's and 3 'b's, and avoids the sequences 'aaa' and 'bbb', hence meeting all the criteria requested.

Solution Implementation

1class Solution:
2    def str_without_3a3b(self, a: int, b: int) -> str:
3        # Start with an empty list to store the result
4        result = []
5      
6        # Continue until either 'a' or 'b' runs out
7        while a and b:
8            # If 'a's are more, add 'aab' to result
9            if a > b:
10                result.append('aab')
11                a -= 2  # Use -= operator for better readability
12                b -= 1
13            # If 'b's are more, add 'bba' to result
14            elif a < b:
15                result.append('bba')
16                a -= 1
17                b -= 2
18            # If 'a' and 'b' are equal, add 'ab' to result
19            else:
20                result.append('ab')
21                a -= 1
22                b -= 1
23      
24        # If 'a's are left, append them to result as they will not violate the condition
25        if a:
26            result.append('a' * a)  # Multiple 'a's by remaining count
27      
28        # If 'b's are left, append them to result as they will not violate the condition
29        if b:
30            result.append('b' * b)  # Multiple 'b's by remaining count
31      
32        # Combine the elements of the list into a single string and return
33        return ''.join(result)
34

1class Solution {
2
3    // Method to create a string that follows the condition of not having more than two consecutive 'a' or 'b'
4    public String strWithout3a3b(int aCount, int bCount) {
5        // StringBuilder to construct the result string efficiently
6        StringBuilder result = new StringBuilder();
7
8        // Loop until one of aCount or bCount becomes 0
9        while (aCount > 0 && bCount > 0) {
10            // If there are more 'a's left, append "aab" to the result
11            if (aCount > bCount) {
12                result.append("aab");
13                aCount -= 2; // Used two 'a's
14                bCount -= 1; // Used one 'b'
15            } 
16            // If there are more 'b's left, append "bba" to the result
17            else if (aCount < bCount) {
18                result.append("bba");
19                aCount -= 1; // Used one 'a'
20                bCount -= 2; // Used two 'b's
21            } 
22            // If the number of 'a' and 'b' is equal, append "ab" to the result
23            else {
24                result.append("ab");
25                aCount -= 1; // Used one 'a'
26                bCount -= 1; // Used one 'b'
27            }
28        }
29
30        // If any 'a's are left, append all remaining 'a's at the end.
31        // Repeat 'a' the number of times that are left
32        while (aCount > 0) {
33            result.append("a");
34            aCount--;
35        }
36
37        // If any 'b's are left, append all remaining 'b's at the end.
38        // Repeat 'b' the number of times that are left
39        while (bCount > 0) {
40            result.append("b");
41            bCount--;
42        }
43      
44        // Convert the StringBuilder to a string and return
45        return result.toString();
46    }
47}
48

1class Solution {
2public:
3    // Generates a string where "a" and "b" are not repeated more than twice consecutively
4    string strWithout3a3b(int countA, int countB) {
5        string result;
6      
7        // Loop as long as both a and b have at least one remaining
8        while (countA > 0 && countB > 0) {
9            if (countA > countB) {
10                // If we have more 'a's, append "aab"
11                result += "aab";
12                countA -= 2;
13                countB -= 1;
14            } else if (countA < countB) {
15                // If we have more 'b's, append "bba"
16                result += "bba";
17                countA -= 1;
18                countB -= 2;
19            } else {
20                // If the counts are equal, append "ab"
21                result += "ab";
22                --countA;
23                --countB;
24            }
25        }
26      
27        // If 'a's are left, append all remaining 'a's
28        if (countA > 0) {
29            result += string(countA, 'a');
30        }
31        // If 'b's are left, append all remaining 'b's
32        if (countB > 0) {
33            result += string(countB, 'b');
34        }
35      
36        // Return the final string
37        return result;
38    }
39};
40

1// Generates a string where "a" and "b" are not repeated more than twice consecutively
2function strWithout3a3b(countA: number, countB: number): string {
3    let result: string = '';
4
5    // Loop as long as both a and b have at least one remaining
6    while (countA > 0 && countB > 0) {
7        if (countA > countB) {
8            // If we have more 'a's, append "aab"
9            result += 'aab';
10            countA -= 2;
11            countB -= 1;
12        } else if (countA < countB) {
13            // If we have more 'b's, append "bba"
14            result += 'bba';
15            countA -= 1;
16            countB -= 2;
17        } else {
18            // If the counts are equal, append "ab"
19            result += 'ab';
20            countA--;
21            countB--;
22        }
23    }
24  
25    // If 'a's are left, append all remaining 'a's
26    if (countA > 0) {
27        result += 'a'.repeat(countA);
28    }
29    // If 'b's are left, append all remaining 'b's
30    if (countB > 0) {
31        result += 'b'.repeat(countB);
32    }
33  
34    // Return the final string
35    return result;
36}
37

Time and Space Complexity

The given Python code generates a string where 'a's and 'b's are not in groups of three consecutively by iterating through the counts of 'a's and 'b's.

Time Complexity

The time complexity of the code primarily depends on the number of iterations of the while-loop, which holds true while both a and b are positive. Within each iteration, the conditionals will execute in constant time, and either a or b, or both are reduced by at least one.

In the worst-case scenario, a and b are equal, and each iteration reduces them by 1. As such, the loop runs a maximum of max(a, b) times. After the while-loop, appending the remaining 'a's or 'b's happens in linear time relative to the remaining amount of a or b. Therefore, the worst-case time complexity is O(max(a, b)).

Space Complexity

The space complexity is primarily determined by the output space required for the answer string. As a and b decrease, elements are continuously appended to the ans list. This list can contain at most a + b entries (when the final counts of a and b are appended as single characters). No additional significant space is used, so the space complexity is also O(a + b), equivalent to the length of the generated string.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: