Sponsored
Sponsored
This approach constructs the string by always choosing the majority character until we need to switch to prevent three consecutive characters.
Steps:
Time Complexity: O(a + b) because each character is processed once.
Space Complexity: O(a + b) for the result string.
1#include <iostream>
2#include <string>
3
4std::string strWithout3a3b(int a, int b) {
5 std::string res;
6 while (a > 0 || b > 0) {
7 bool writeA = false;
8 int n = res.size();
9 if (n >= 2 && res[n-1] == res[n-2]) {
10 if (res[n-1] == 'b') writeA = true;
11 } else {
12 if (a >= b) writeA = true;
13 }
14
15 if (writeA) {
16 res += 'a';
17 a--;
18 } else {
19 res += 'b';
20 b--;
21 }
22 }
23 return res;
24}
25
26int main() {
27 int a = 4, b = 1;
28 std::cout << strWithout3a3b(a, b) << std::endl;
29 return 0;
30}This C++ solution uses a dynamic string to construct the required sequence. It checks the last two characters and decides whether to append 'a' or 'b' based on the majority rule while avoiding consecutive triplets.
This approach leverages an interleaving strategy to distribute characters evenly and avoid consecutive identical sequences.
Steps:
Time Complexity: O(a + b) due to iteration through characters.
Space Complexity: O(a + b) used for the output string.
This C solution follows a clear pattern by interleaving the characters carefully based on their counts. It constructs the string by focusing on avoiding 'aaa' or 'bbb' through interleaving up to two of the more frequent characters with one of the weaker.