Construct string having all possible strings of K letters as subsequence
Given two positive integers, let’s denote them as N and K. The task is to construct a string S such that all possible strings of length N formed using the first K lowercase English alphabets, appear as subsequences of S.
In case there exist multiple valid solutions, the objective is to output the solution with the minimal length. If there are still several valid possibilities with the same minimal length, any of them can be selected as the output.
Examples:
Input: N = 2, K = 3
Output: abcbac
Explanation: abcbac being the smallest string can be broken down into (aa, ab, ac, ba, bb, bc, ca, cb, cc) which are all the subsequences of given string “abcbac”.Input: N = 3, K = 1
Output: aaa
Explanation: aaa is the smallest string that can be made so that (aaa) occurs in it.
Approach: To solve the problem, follow the below idea:
The minimum length required for the string S is given by the product of N and K (N * K). This ensures that there are enough characters to accommodate all possible subsequences of length N using the initial K lowercase English alphabets.
To construct the string meeting the specified conditions, create a pattern consisting of K different characters (a1, a2, …, ak) and repeat this pattern N times to form the string.
Step-by-step algorithm:
- Declare a string variable S to store the answer string.
- Run an outer loop for N times.
- Inside the outer loop append first K characters to S.
- After all the iterations, print the final string S.
Below is the implementation of the algorithm:
Java
public class Main { // Define some constants static final char nline = '\n' ; static final int MOD = 1000000007 ; // Function to solve the problem static void solve() { int n, k; n = 2 ; k = 3 ; StringBuilder s = new StringBuilder(); // Nested loops to construct the desired string for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < k; j++) { // Append characters to the string in a specific pattern s.append(( char )( 'a' + j)); } } // Print the constructed string System.out.println(s.toString() + nline); } // Main function public static void main(String[] args) { solve(); } } // This code is contributed by shivamgupta310570 |
C#
using System; class Program { // Main function static void Main( string [] args) { Solve(); // Call the Solve function } // Function to solve the problem static void Solve() { int n = 2; int k = 3; string s = "" ; // Nested loops to construct the desired string for ( int i = 0; i < n; i++) { for ( int j = 0; j < k; j++) { // Append characters to the string in a specific pattern s += ( char )( 'a' + j); } } // Print the constructed string Console.WriteLine(s); } } |
Javascript
// Javascript program for the above approach // Define some constants const nline = '\n' ; const MOD = 1000000007; // Function to solve the problem function solve(){ let n = 2; let k = 3; let s = '' ; // Nested loops to construct the desired string for (let i = 0; i < n; i++) { for (let j = 0; j < k; j++) { // Append characters to the string in a specific // pattern s += String.fromCharCode( 'a' .charCodeAt(0) + j); } } // Print the constructed string console.log(s + nline); } // Main function solve() // This code is contributed by Susobhan Akhuli |
C++14
#include <bits/stdc++.h> using namespace std; // Define some constants #define nline '\n' #define MOD 1000000007 #define f(i, n) for (int i = 0; i < n; i++) // Function to solve the problem void solve() { int n, k; n = 2; k = 3; string s; // Nested loops to construct the desired string for ( int i = 0; i < n; i++) { for ( int j = 0; j < k; j++) { // Append characters to the string in a specific // pattern s += 'a' + j; } } // Print the constructed string cout << s << nline; } // Main function signed main() { solve(); } |
Python3
# Python Implementation # Function to solve the problem def solve(): n = 2 k = 3 s = "" # Nested loops to construct the desired string for i in range (n): for j in range (k): # Append characters to the string in a specific pattern s + = chr ( ord ( 'a' ) + j) # Print the constructed string print (s) # Main function if __name__ = = "__main__" : solve() # This code is contributed by Tapesh(tapeshdu420) |
abcabc
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)