Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Code in C++
4.1.
Time Complexity 
4.2.
Space Complexity 
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Gaurish Anand
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Problems related to substrings and subsequences that satisfy particular constraints are commonly asked in Amazon, Microsoft, and Adobe. In this article, we will discuss one of those problems. 

Before beginning with this question, let’s recap what a substring of a string is. A substring is a contiguous part of a string placed between two specified indices. For example, non-empty substrings of the string “abc” are “a”, “b”, “c”, ”ab”, “bc”, and “abc”.

Note - A string a (of the same length) is lexicographically smaller than a string b if the first element from the left where a and b differ, string a has a letter that appears first in the alphabetical order than the corresponding letter in b. For example, "9658" is lexicographically smaller than "9690" because the first position they differ in is at the third letter, and '5' comes before '9'.

Problem Statement

Given integers N and K, find the Kth lexicographically smallest string of integers of length N such that the product of digits for each substring is unique. Return -1 if no such string of integers exists. Example: 

Input: N = 1    K = 9
Output: 8
Explanation: The valid strings of length 1 are 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The string “8” is the 9th lexicographically smallest string among them.

Input: N = 1    K = 14
Output: -1
Explanation: There are only 10 valid strings of length 1.

Input: N = 3    K = 5
Output: 239
Explanation: The valid strings of length 3 are 234, 235, 237, 238, 239, 243 …, etc. The string “239” is the 5th lexicographically smallest string among them and we can check that it is valid as the product of all the substrings is unique which are: {2,3,9,6,27,54}.

Why we did not consider the string “123” as valid? Let’s check. 
The product of all its substrings are: {1,2,3,1x2=2,2x3=6,1x2x3=6}. You can see that the products are not unique. Hence, this string is not valid.

Also see, Euclid GCD Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}


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(8N), 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(8N), where N = array's length. It is because we will have in total 8N 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 -

 

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!

Live masterclass