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.
1public class StringWithoutAAAorBBB {
2 public static String strWithout3a3b(int a, int b) {
3 StringBuilder res = new StringBuilder();
4 while (a > 0 || b > 0) {
5 boolean writeA = false;
6 int n = res.length();
7 if (n >= 2 && res.charAt(n-1) == res.charAt(n-2)) {
8 if (res.charAt(n-1) == 'b') writeA = true;
9 } else {
10 if (a >= b) writeA = true;
11 }
12
13 if (writeA) {
14 res.append('a');
15 a--;
16 } else {
17 res.append('b');
18 b--;
19 }
20 }
21 return res.toString();
22 }
23
24 public static void main(String[] args) {
25 int a = 4, b = 1;
26 System.out.println(strWithout3a3b(a, b));
27 }
28}This Java solution utilizes a StringBuilder to dynamically form the desired output string while ensuring no 'aaa' or 'bbb' substring exists. The choice of character is based on existing counts and recent characters added.
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.
using System.Text;
public class Solution {
public string StrWithout3a3b(int a, int b) {
StringBuilder result = new StringBuilder();
while (a > 0 || b > 0) {
if (a > b) {
if (a > 0) { result.Append('a'); a--; }
if (a > 0) { result.Append('a'); a--; }
if (b > 0) { result.Append('b'); b--; }
} else {
if (b > 0) { result.Append('b'); b--; }
if (b > 0) { result.Append('b'); b--; }
if (a > 0) { result.Append('a'); a--; }
}
}
return result.ToString();
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.StrWithout3a3b(4, 1));
}
}This C# solution applies a structured pattern that systematically processes the counts of 'a' and 'b', ensuring that their interleave does not form consecutive sequences of more than two 'a's or 'b's.