Min Length String with All Substrings of Size N
Given two integers N and K, the task is to find the string S of minimum length to contain all possible strings of size N as a substring. The characters of the string should be from integers ranging from 0 to K-1.
Examples:
Input: N = 2, K = 2
Output: 00110
Explanation: Allowed characters are from 0 to k-1 (i.e., 0 and 1). There are 4 string possible of size N=2 (i.e “00”, “01”,”10″,”11″) “00110” contains all possible string as a substring. It also has the minimum length.Input: N = 2, K = 3
Output: 0010211220
Explanation: Allowed characters are from 0 to k-1 (i.e., 0, 1 and 2). There are total 9 strings possible of size N, given output string has the minimum length that contains all those strings as substring.
Approach: To solve the problem follow the below idea:
In this we find the smallest string of length N using digits from 0 to K-1, such that it contains all possible strings of size N as substrings. The solution utilizes a approach to iteratively build the string while ensuring that all permutations of size N are present as substrings.
- Initialize an empty string ans with N zeros.
- Decrement K by 1 to represent the range of digits from 0 to K-1.
- Create an unordered set visited to keep track of visited nodes and insert the initial string into it.
- Run a loop until all permutations are found, i.e., the size of the visited set equals (K+1)^N.
- Extract the last N-1 digits from the current string ans and store them in the previous string.
- Iterate from K to 0.
- Create a new string currStr equal to the previous and push i into it.
- If currStr is not in the visited set, insert it into the set, append the current digit to the current string ans, and break from the loop.
- Return the ans string.
Implementation of the above approach:
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the lexicographically smallest
// string of length N using K digits
string findString(int n, int k)
{
// Initialize the result string with '0'
string ans = "0";
// Decrement k for 0-based indexing
k -= 1;
// Set to store visited strings
unordered_set<string> visited;
visited.insert("0");
// Loop until all possible strings are generated
while (visited.size() < pow((k + 1), n)) {
// Get the substring for the previous n-1
// characters
string previous = ans.substr(ans.length() - n + 1);
// Iterate from k to 0 to find the
// lexicographically smallest character
for (int i = k; i >= 0; i--) {
string currStr = previous + to_string(i);
// If the current string is not visited,
// insert it and append to the result
if (visited.find(currStr) == visited.end()) {
visited.insert(currStr);
ans += to_string(i);
break;
}
}
}
return ans;
}
// Driver code
int main()
{
// Set values for N and K
int n = 2;
int k = 2;
// Call the findString method to obtain the result
string result = findString(n, k);
// Print the result
cout << "Lexicographically smallest string: " << result
<< endl;
return 0;
}
// This code is contributed by Susobhan Akhuli
import java.util.HashSet;
import java.util.Set;
public class GFG {
// Function to find the lexicographically smallest
// string of length N using K digits
public static String findString(int n, int k) {
// Initialize the result string with '0'
StringBuilder ans = new StringBuilder("0");
// Decrement k for 0-based indexing
k -= 1;
// Set to store visited strings
Set<String> visited = new HashSet<>();
visited.add("0");
// Loop until all possible strings are generated
while (visited.size() < Math.pow((k + 1), n)) {
// Get the substring for the previous n-1 characters
String previous = ans.substring(ans.length() - n + 1);
// Iterate from k to 0 to find the lexicographically
// smallest character
for (int i = k; i >= 0; i--) {
String currStr = previous + i;
// If the current string is not visited,
// insert it and append to the result
if (!visited.contains(currStr)) {
visited.add(currStr);
ans.append(i);
break;
}
}
}
return ans.toString();
}
// Driver code
public static void main(String[] args) {
// Set values for N and K
int n = 2;
int k = 2;
// Call the findString method to obtain the result
String result = findString(n, k);
// Print the result
System.out.println("Lexicographically smallest string: " + result);
}
}
using System;
using System.Collections.Generic;
class Program
{
// Function to find the lexicographically smallest
// string of length N using K digits
static string FindString(int n, int k)
{
// Initialize the result string with '0'
string ans = "0";
// Decrement k for 0-based indexing
k -= 1;
// Set to store visited strings
HashSet<string> visited = new HashSet<string>();
visited.Add("0");
// Loop until all possible strings are generated
while (visited.Count < Math.Pow((k + 1), n))
{
// Get the substring for the previous n-1
// characters
string previous = ans.Substring(ans.Length - n + 1);
// Iterate from k to 0 to find the
// lexicographically smallest character
for (int i = k; i >= 0; i--)
{
string currStr = previous + i.ToString();
// If the current string is not visited,
// insert it and append to the result
if (!visited.Contains(currStr))
{
visited.Add(currStr);
ans += i.ToString();
break;
}
}
}
return ans;
}
// Driver code
static void Main()
{
// Set values for N and K
int n = 2;
int k = 2;
// Call the FindString method to obtain the result
string result = FindString(n, k);
// Print the result
Console.WriteLine("Lexicographically smallest string: " + result);
}
}
function findString(n, k) {
// Initialize the result string with '0'
let ans = "0";
// Decrement k for 0-based indexing
k -= 1;
// Set to store visited strings
let visited = new Set();
visited.add("0");
// Loop until all possible strings are generated
while (visited.size < Math.pow(k + 1, n)) {
// Get the substring for the previous n-1 characters
let previous = ans.substring(ans.length - n + 1);
// Iterate from k to 0 to find the lexicographically
// smallest character
for (let i = k; i >= 0; i--) {
let currStr = previous + i;
// If the current string is not visited,
// insert it and append to the result
if (!visited.has(currStr)) {
visited.add(currStr);
ans += i;
break;
}
}
}
return ans;
}
// Set values for N and K
let n = 2;
let k = 2;
// Call the findString method to obtain the result
let result = findString(n, k);
// Print the result
console.log("Lexicographically smallest string: " + result);
def findString(n, k):
ans = "0"
k -= 1
visited = set()
visited.add("0")
while len(visited) < pow((k + 1), n):
previous = ans[-n + 1:]
for i in range(k, -1, -1):
currStr = previous + str(i)
if currStr not in visited:
visited.add(currStr)
ans += str(i)
break
return ans
# Driver code
n = 2
k = 2
result = findString(n, k)
print("Lexicographically smallest string:", result)
Output
Lexicographically smallest string: 0110
Time Complexity: O(KN N), As we are running the loop of size O(KN N).
Auxiliary Space: O(KN N), As we have the set to store the all the possible permutations.
Contact Us