Find the Kth lexicographically smallest string with unique products for all the substrings

Approach

We can solve this problem using recursion. We will recursively check all the possible numeric strings of length N and find the Kth valid numeric string. Some of the observations before going to the solution: 

1. Since the product of all the substrings should be unique, no digit should be repeated in the numeric string. 
2. If N>10, the answer will be “-1” straightaway since we only have 10 unique digits(0 to 9) and for any string of length>10 at least one of the digits will get repeated which violates condition 1.
3. If N=1, K can’t exceed 10 because there are only 10 valid strings of length 1 (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9).
4. If 1<N<10, then we can’t have ‘0’ or ‘1’ as digits in the numeric string as then the product of some substrings will repeat.(You can check this condition by working out some examples on your own on strings like “1230”,”123”,”540” etc.)
   1. To find the Kth lexicographically smallest string, in this case, start recursively and insert digits from ‘2’ to ‘9’ at each index. 
   2. Maintain a map to store the products of all the substrings inserted until the previous index. 
   3. While inserting a digit, find the products of all the subarrays ending at the current index and check that the product should not be repeated in the map. If no product is repeated, recursively fill the leftover indices.

Code in C++

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

// This function will return the Kth smallest string of length N 
// It will -1 if no such string exists.
string findKthSmallestStringHelper(int index,string& ans,int& K,unordered_map<int,int>& products){
	if(index==ans.size()){
		// All the positions are filled now
		K--;
		if(K==0){
			// This current string is the Kth smallest ans
			return ans;
		}else{
			return "-1";
		}
	}

	// try to insert numbers from '2' to '9' one by one and check if it will be valid string or not
	for(int i=2;i<=9;i++){
		char digit = i + '0';

		// check if inserting this current digit, doesn't produce a substring with the same product
		bool flag = true; // This boolean will maintain if this digit can be inserted or not 
		unordered_map<int,int> new_products;
		
		int currentProduct = i;
		new_products[currentProduct]++;
		if(products.count(currentProduct)){
			flag = false;
		}
		
		for(int j=index-1;j>=0;j--){
			currentProduct = currentProduct*(ans[j]-'0');
			new_products[currentProduct]++;
			if(products.count(currentProduct)){
				flag = false;
			}
		}

		if(flag){
			// current digit can be inserted
			ans[index] = digit;
			for(auto it:new_products){
				int key = it.first;
				int value = it.second;
				products[key] += value;
			}
			string s = findKthSmallestStringHelper(index+1,ans,K,products);
			if(s!="-1"){
				return s;
			}
			for(auto it:new_products){
				int key = it.first;
				int value = it.second;
				products[key] -= value;
				if(products[key]==0){
					products.erase(key);
				}
			}
		}
	}
	return "-1";
}

string findKthSmallestString(int N,int K){
	if(N>10){
		// no string possible whose product of all substring will be unique
		return "-1";
	}
	else if(N==1){
		// all the possible substrings of length 1 will be :
		// "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
		if(K<=10){
			string ans = "";
			ans += '0'+(K-1);
			return ans;
		}else{
			return "-1";
		}
	}
	else{
		// form a string of size N and fill the digits one by one at each 
		// index to find the kth smallest number
		string ans;
		ans.append(N,'\0'); 
		unordered_map<int,int> products;
		return findKthSmallestStringHelper(0,ans,K,products);
	}
}
int main(){
	int n1 = 1, k1 = 10;
	cout<<k1<<"th lexicographically smallest string of numbers of length "<<n1<<" is: "<<findKthSmallestString(n1,k1)<<endl;

	int n2 = 3, k2 = 5;
	cout<<k2<<"th lexicographically smallest string of numbers of length "<<n2<<" is: "<<findKthSmallestString(n2,k2)<<endl;

	int n3 = 3, k3 = 6;
	cout<<k3<<"th lexicographically smallest string of numbers of length "<<n3<<" is: "<<findKthSmallestString(n3,k3)<<endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

10th lexicographically smallest string of numbers of length 1 is: 9
5th lexicographically smallest string of numbers of length 3 is: 239
6th lexicographically smallest string of numbers of length 3 is: 243

Time Complexity 

Since we can insert 8 digits (‘2’ to ‘9’) at every place, the time complexity is O(8^N), where N = size of the integer.

Space Complexity 

Since we will be storing the product of all substrings of a string of size N in a hashmap, the space complexity is O(8^N), where N = array's length. It is because we will have in total 8^N substring for a string of size N, and each substring will have a unique product. 
Check out this problem - Longest String Chain

Frequently Asked Questions

1.What is the difference between a subsequence and a subarray (or substring in the case of a string)?

A subsequence is formed by deriving 0 or more elements from a sequence without changing the relative order of the elements in the original sequence. In comparison, a subarray is a contiguous part of a sequence. Therefore all the subarray will be subsequences too of a sequence, but vice versa is not true. For example: [1,2,4] is a subsequence for the sequence [1,2,3,4], but it is not the subarray.

2.How is an unordered_map implemented in C++?

Unordered_map is implemented using hash tables where keys are hashed into indices of a hash table so that the insertion is always randomized.

3.What is the difference between an unordered map and an ordered map?

A map (like a set) contains a sorted list of unique keys, whereas an unordered map contains a list of unique keys that may or may not be sorted. The time complexity of insertion and searching in a map is O(log N), whereas, in unordered_map, it is O(1).

4.Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?

Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.

Key Takeaways

In this article, we learned to find the Kth lexicographically smallest string of integers of length N such that the product of digits for each substring is unique. Since questions related to strings are frequently asked in interviews, we recommend you practice more problems based on strings on Coding Ninjas Studio.

Also check out - Substr C++

Recommended problems -

• Find the Shortest Substring in a String
• Subsequence of a String
• Beautiful String

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!