984. String Without AAA or BBB

MediumGreedyString
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm should you use to find a node that is close to the root of the tree?

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:

  1. Initialize an empty list ans that will contain blocks of the final string.

  2. Enter a while loop that continues as long as both a and b have remaining characters (i.e., a > 0 and b > 0).

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

  4. 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'.

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

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

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

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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:

  1. Initialize the list ans as empty. This will hold the pieces of our final string.

  2. Enter the while loop since both a (4) and b (3) are greater than 0.

  3. 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).

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

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

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

  7. 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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫