Find a string of minimum length containing exactly N occurrences of AB Subsequences
Given an integer N. The task is to print a minimum possible length string such that there must be exactly N occurrences of “AB” subsequences.
Examples:
Input: N = 5
Output: AABAB
Explanation: String “AABAB” contains exactly 5 occurrences of subsequence “AB” and has minimum length also.Input: N = 4
Output: AABB
Explanation: It can be verified that String “AABB” is the smallest strings with 4 occurrence of AB.
Approach: Implement the idea below to solve the problem
We can observe that the maximum number of “AB” subsequences are possible when we have equal number of “A” followed by equal number of “B”. So, if we have X number of “A” followed by X number of “B”, then the total number of “AB” subsequences are X * X. So, we can find the nearest perfect square, which is smaller than or equal to N, say S and then place sqrt(S) number of “A” followed by sqrt(S) number of “B”. Now according to the difference between N and S (diff), we can have three cases:
- Case 1: (diff == 0), no more subsequences of “AB” are needed.
- Case 2: (diff <= K), so we can add a single “A” at (last – diff) index among the continuous “B”s.
- Case 3: (diff > K), so we can add one more “A” before the continuous segment of “B” and now the remaining diff will be less than K, so we can add a single “A” at (last – diff) index among the continuous “B”.
Solve for these cases to get the answer.
Step-by-step approach:
- Calculate Square Root of N
- Calculate the difference between N and the square of K is calculated as
diff = (N - K*K)
. The variableext
is initialized to handle the different cases. - Depending on the value of diff, ext is adjusted accordingly to handle the three cases discussed earlier.
- The length of the string is calculated based on the values of K and ext.
- The string is generated and printed character by character based on the conditions specified for ‘A’ and ‘B’.
Below is the implementation of the above approach:
C++
#include <iostream> #include <cmath> using namespace std; // Method to output the required string void Solve( int N) { // Calculate the square root of N and initialize // variables int k = static_cast < int >( sqrt (N)), diff = N - k * k, ext = 0; // Check conditions to determine the values of 'ext' // and 'diff' if (diff > k) { ext = 2; diff -= k; } else if (diff > 0) { ext = 1; } // Calculate the length of the output string int len = 2 * k + ext; // Print the required string based on conditions for ( int i = 0; i < len; i++) { if (i < k) { cout << 'A' ; } else if (ext == 2 && i == k) { cout << 'A' ; } else if (diff > 0 && i == len - diff - 1) { cout << 'A' ; } else { cout << 'B' ; } } } // Driver Function int main() { // Input int N = 5; // Function call to Solve method Solve(N); return 0; } |
Java
// Java code to implement the approach // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Input int N = 5 ; // Function call to Solve method Solve(N); } // Method to output the required string public static void Solve( int N) { // Calculate the square root of N and initialize // variables int k = ( int )Math.sqrt(N), diff = N - k * k, ext = 0 ; // Check conditions to determine the values of 'ext' // and 'diff' if (diff > k) { ext = 2 ; diff -= k; } else if (diff > 0 ) { ext = 1 ; } // Calculate the length of the output string int len = 2 * k + ext; // Print the required string based on conditions for ( int i = 0 ; i < len; i++) { if (i < k) { System.out.print( 'A' ); } else if (ext == 2 && i == k) { System.out.print( 'A' ); } else if (diff > 0 && i == len - diff - 1 ) { System.out.print( 'A' ); } else { System.out.print( 'B' ); } } } } |
Python3
import math # Method to output the required string def solve(N): # Calculate the square root of N and initialize variables k = int (math.sqrt(N)) diff = N - k * k ext = 0 # Check conditions to determine the values of 'ext' and 'diff' if diff > k: ext = 2 diff - = k elif diff > 0 : ext = 1 # Calculate the length of the output string length = 2 * k + ext # Print the required string based on conditions for i in range (length): if i < k: print ( 'A' , end = '') elif ext = = 2 and i = = k: print ( 'A' , end = '') elif diff > 0 and i = = length - diff - 1 : print ( 'A' , end = '') else : print ( 'B' , end = '') # Driver Function if __name__ = = "__main__" : # Input N = 5 # Function call to Solve method solve(N) |
C#
using System; public class GFG { public static void Main( string [] args) { // Input int N = 5; // Function call to Solve method Solve(N); } // Method to output the required string public static void Solve( int N) { // Calculate the square root of N and initialize // variables int k = ( int )Math.Sqrt(N), diff = N - k * k, ext = 0; // Check conditions to determine the values of 'ext' // and 'diff' if (diff > k) { ext = 2; diff -= k; } else if (diff > 0) { ext = 1; } // Calculate the length of the output string int len = 2 * k + ext; // Print the required string based on conditions for ( int i = 0; i < len; i++) { if (i < k) { Console.Write( 'A' ); } else if (ext == 2 && i == k) { Console.Write( 'A' ); } else if (diff > 0 && i == len - diff - 1) { Console.Write( 'A' ); } else { Console.Write( 'B' ); } } } } |
Javascript
// Method to output the required string function Solve(N) { // Calculate the square root of N and initialize // variables let k = Math.floor(Math.sqrt(N)); let diff = N - k * k; let ext = 0; // Check conditions to determine the values of 'ext' // and 'diff' if (diff > k) { ext = 2; diff -= k; } else if (diff > 0) { ext = 1; } // Calculate the length of the output string let len = 2 * k + ext; // Print the required string based on conditions for (let i = 0; i < len; i++) { if (i < k) { console.log( 'A' ); } else if (ext === 2 && i === k) { console.log( 'A' ); } else if (diff > 0 && i === len - diff - 1) { console.log( 'A' ); } else { console.log( 'B' ); } } } // Driver Function function main() { // Input let N = 5; // Function call to Solve method Solve(N); } // Execute the main function main(); |
AABAB
Time Complexity: Sqrt(N)
Auxiliary space: O(1)
Contact Us