Construct a string that contains a times letter ‘A’ and b times letter ‘B’ (a > b) such that the maximum continuous occurrence of a letter is as small as possible.
Examples:
Input: a = 4, b = 3
Output: ABABABA
Explanation: The other possible ways could be “AAAABBB” or “AABBAAB” etc.
But “ABABABA” is the most optimum solution with minimum consecutive occurrence.Input: a = 5, b = 1
Output: AABAAA
Approach: The approach of the problem is based on the below observation:
Since a > b, it can be easily observed that ‘B’ is dividing the whole string in (b+1) parts.
According to the pigeonhole principle, at least one region must have at least p = ?a/(b+1)? A’s. First, place p number of ‘A’ in every (b+1) region. Now remaining ‘A’s can be equally distributed in the regions.
Follow the below steps to solve the problem:
- The region is divided into (b+1) parts. So run a loop from 0 to (b+1) and start inserting for each part.
- First, calculate what should be the current value of insertion of ‘A’ (Using the Pigeonhole principle p = ceil(a/(b+1)) ) for each left region.
- Insert p times ‘A’ in the string and decrement the value of a.
- Now one region is completed, so insert a ‘B’ and decrement the value of b.
- Keep doing this till constraints of a and b allow you to do so.
- Return the final string as the answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to construct the stringstring generateans(int a, int b){ int temp = b + 1; string s; // Run a loop until b is greater than 0 while (temp--) { int each = a / (b + 1); while (each--) { s.push_back('A'); a--; } if (b > 0) { s.push_back('B'); b--; } } return s;}// Driver codeint main(){ int a = 4, b = 3; // Function call cout << generateans(a, b); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to construct the string public static String generateans(int a, int b) { int temp = b + 1; String s = ""; // Run a loop until b is greater than 0 while (temp-- > 0) { int each = a / (b + 1); while (each-- > 0) { s += 'A'; a--; } if (b > 0) { s += 'B'; b--; } } return s; } // Driver Code public static void main(String[] args) { int a = 4, b = 3; // Function call System.out.print(generateans(a, b)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# Function to construct the stringdef generateans(a, b): temp = b + 1 s = "" # Run a loop until b is greater than 0 while temp>0: each = (a // (b + 1)) while each>0: s += 'A' a -= 1 each -= 1 if (b > 0): s += 'B' b -= 1 temp -= 1 return s# Driver codea,b = 4,3# Function callprint(generateans(a, b))# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;using System.Linq;public class GFG{ // Function to construct the string public static string generateans(int a, int b) { int temp = b + 1; string s = ""; // Run a loop until b is greater than 0 while (temp-- > 0) { int each = a / (b + 1); while (each-- > 0) { s += 'A'; a--; } if (b > 0) { s += 'B'; b--; } } return s; } // Driver Code public static void Main(string[] args) { int a = 4, b = 3; // Function call Console.WriteLine(generateans(a, b)); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code to implement the approach // Function to construct the string const generateans = (a, b) => { let temp = b + 1; let s = ""; // Run a loop until b is greater than 0 while (temp--) { let each = parseInt(a / (b + 1)); while (each--) { s += 'A'; a--; } if (b > 0) { s += 'B'; b--; } } return s; } // Driver code let a = 4, b = 3; // Function call document.write(generateans(a, b));// This code is contributed by rakeshsahni</script> |
Output
ABABABA
Time Complexity: O(a+b)
Auxiliary Space: O(a+b) because extra space is used for string s
Another approach:
We can start by appending ‘AB’ pairs until we are left with only ‘a-b’ ‘A’ characters. Then, we can append remaining ‘A’ characters at the end. This will give us the desired string with minimum consecutive occurrence.
C++
#include <bits/stdc++.h>using namespace std;string generateans(int a, int b) { string s = ""; int countA = a, countB = b; bool appendA = true; while (countA > 0 || countB > 0) { if (appendA) { s += 'A'; countA--; } else { s += 'B'; countB--; } if (countB == 0 && countA > 0) { s += 'A'; countA--; } else if (countA == 0 && countB > 0) { s += 'B'; countB--; } else if (countA > countB) { appendA = true; } else { appendA = false; } } return s;}int main() { int a = 4, b = 3; cout << generateans(a, b) << endl; return 0;} |
Java
// Java program to implement the above approach import java.util.*;public class Main { public static String generateans(int a, int b) { StringBuilder s = new StringBuilder(); int countA = a, countB = b; boolean appendA = true; while (countA > 0 || countB > 0) { if (appendA) { s.append('A'); countA--; } else { s.append('B'); countB--; } if (countB == 0 && countA > 0) { s.append('A'); countA--; } else if (countA == 0 && countB > 0) { s.append('B'); countB--; } else if (countA > countB) { appendA = true; } else { appendA = false; } } return s.toString(); } public static void main(String[] args) { int a = 4, b = 3; System.out.println(generateans(a, b)); }}// Contributed by adityasha4x71 |
Python3
# Pyhton program to implement the above approach def generateans(a, b): s = "" countA, countB = a, b appendA = True while countA > 0 or countB > 0: if appendA: s += 'A' countA -= 1 else: s += 'B' countB -= 1 if countB == 0 and countA > 0: s += 'A' countA -= 1 elif countA == 0 and countB > 0: s += 'B' countB -= 1 elif countA > countB: appendA = True else: appendA = False return sa, b = 4, 3print(generateans(a, b))# Contributed by adityasha4x71 |
C#
using System;public class Program { public static string GenerateAns(int a, int b) { string s = ""; int countA = a, countB = b; bool appendA = true; while (countA > 0 || countB > 0) { if (appendA) { s += 'A'; countA--; } else { s += 'B'; countB--; } if (countB == 0 && countA > 0) { s += 'A'; countA--; } else if (countA == 0 && countB > 0) { s += 'B'; countB--; } else if (countA > countB) { appendA = true; } else { appendA = false; } } return s; } public static void Main() { int a = 4, b = 3; Console.WriteLine(GenerateAns(a, b)); }} |
Javascript
// JavaScript program to implement the above approachfunction generateans(a, b) { let s = ""; let countA = a, countB = b; let appendA = true; while (countA > 0 || countB > 0) { if (appendA) { s += 'A'; countA--; } else { s += 'B'; countB--; } if (countB == 0 && countA > 0) { s += 'A'; countA--; } else if (countA == 0 && countB > 0) { s += 'B'; countB--; } else if (countA > countB) { appendA = true; } else { appendA = false; } } return s;}// Driver codelet a = 4, b = 3;console.log(generateans(a, b)); |
Output
ABABABA
Time Complexity: O(a+b)
Auxiliary Space: O(a+b)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!