POTD Solutions | 16 Nov’ 23 | Find the String
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Depth First Search (DFS) but will also help you build up problem-solving skills.
POTD 16 November: Find the String:
Given two integers N and K, the task is to find the string S of minimum length such that it contains 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.
Find the String using Depth First Search:
In this, we find the lexicographically 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 employs Depth First Search (DFS) to explore the possibilities and generate the required string.
Step by step approach:
- Check if N is 1, return a string containing all digits from 0 to K-1.
- Initialize the current string
ans
with N zeros. - Insert the initial string into the set and call the
dfs
function to generate the lexicographically smallest string- dfs() function returns a boolean indicating whether all possible strings are generated.
- if the set contains all possible strings, return true.
- Extract the last N-1 digits from the current string
ans
into a string tmp. - Iterate through all possible digits from 0 to K-1.
- push the current digit to the tmp vector.
- If the newly generated string is not in the set, add the digit to the current string, insert the newly generated string into the set, and recursively call the
dfs()
function. - If the recursive call returns true, indicating all possible strings are generated, return true.
- Remove the newly generated string from the set and the added digit from the current string.
- Remove the appended digit from the last N-1 digits.
- Return false.
- Return the ans string.
Below is the implementation of the above approach:
C++
class Solution { public : int K, N; long long tot; // set to store the generated strings set<string> st; // Function to perform depth-first search to generate // all possible strings bool dfs(string& ans) { // if all possible strings are generated, return // true if (st.size() == tot) { return true ; } string tmp = "" ; // get the last N-1 digits of the current string if (N > 1) { tmp = ans.substr(ans.size() - N + 1); } for ( int i = 0; i < K; i++) { // for each possible digit add the digit to the // last N-1 digits tmp.push_back(( char )(i + '0' )); // if the newly generated string is not already // in the set if (st.find(tmp) == st.end()) { // add the digit to the current string ans.push_back( char (i + '0' )); // insert the newly generated string to the // set st.insert(tmp); if (dfs(ans)) return true ; // remove the newly generated string from // the set st.erase(tmp); // remove the added digit from the current // string ans.pop_back(); } // remove the added digit from the last N-1 // digits tmp.pop_back(); } return false ; } // Function to find the lexicographically smallest // string of length N using K digits string findString( int n, int k) { K = k; N = n; // clear the set st.clear(); // if N=1, return a string of all digits from 0 to // K-1 if (n == 1) { string r = "" ; for ( int i = 0; i < k; i++) r.push_back(( char )(i + '0' )); return r; } tot = 1; // calculate total number of possible strings for ( int i = 1; i <= n; i++) tot = (tot * k); // initialize current string with all zeros string ans = string(n, '0' ); st.insert(ans); dfs(ans); return ans; } }; |
Java
class Solution { int K, N; long tot; // HashSet to store visited combinations HashSet<String> st = new HashSet<>(); String ans; boolean dfs() { // If all combinations are visited, return true if (st.size() == tot) { return true ; } String tmp = "" ; // Get the last N-1 digits of the current // combination if (N > 1 ) { tmp = ans.substring(ans.length() - N + 1 ); } for ( int i = 0 ; i < K; i++) { // Append the current digit to the last N-1 // digits of the current combination tmp += i; if (!st.contains(tmp)) { // Append the current digit to the final // combination ans += i; st.add(tmp); // Add the current combination // to the visited combinations if (dfs()) return true ; // Remove the current combination from the // visited combinations st.remove(tmp); // Remove the last digit from the final // combination ans = ans.substring( 0 , ans.length() - 1 ); } // Remove the last digit from the last N-1 // digits of the current combination tmp = tmp.substring( 0 , tmp.length() - 1 ); } // If no valid combination is found, return false return false ; } public String findString( int n, int k) { K = k; N = n; st.clear(); if (n == 1 ) { char [] r = new char [k]; for ( int i = 0 ; i < k; i++) r[i] = ( char )(i + '0' ); return new String(r); } tot = 1 ; // Calculate the total number of possible // combinations for ( int i = 1 ; i <= n; i++) tot = (tot * k); // Create a character array to store the final // combination char [] ansa = new char [n]; Arrays.fill(ansa, '0' ); ans = new String(ansa); st.add(ans); dfs(); return ans; } } |
Python3
class Solution: # Function to perform depth-first search and find the string def dfs( self , ans, d, tot, N, K): global res if len (d) = = tot: # if all combinations have been tried res = ans return True tmp = "" if N > 1 : # get the last N-1 characters of the current string tmp = ans[ len (ans) - N + 1 :] for i in range (K): # # iterate through all possible characters and add the character to the current string tmp + = chr ( 48 + i) # check if the current string is unique if tmp not in d: # add the character to the final answer ans + = chr ( 48 + i) # mark the current string as used d[tmp] = 1 if self .dfs(ans, d, tot, N, K): return True # remove the current string from the dictionary d.pop(tmp) # remove the character from the final answer ans = ans[ 0 : len (ans) - 1 ] # remove the last character from the current string tmp = tmp[ 0 : len (tmp) - 1 ] return False # Function to find the string of length N with K possible characters def findString( self , N, K): # if N is 1, return a string of all possible characters if N = = 1 : r = "" for i in range (K): r + = chr (i + 48 ) return r # total number of possible combinations tot = pow (K, N) ans = '0' * (N) # dictionary to store used strings d = dict () # mark the initial string as used d[ans] = 1 self .dfs(ans, d, tot, N, K) return res |
Time Complexity: O(KN * K), where K is the range of integers and N is the length of substrings
Auxiliary Space: O(KN * N)