DFS Algorithm is a recursive algorithm based on the concept of backtracking. Backtracking is an algorithmic method to address a computational problem that includes searching in every possible combination. It is known for recursively solving problems one step at a time and discarding solutions that do not satisfy the problem constraints at any point in time. It's a sophisticated brute force strategy that tries out all the possible answers before picking the best one.
After reviewing the current path in Backtracking, we must restore the previous state of the visited node by setting visited = false. In contrast, in DFS, the node’s state remains the same so that it is not examined again.
Today we will discuss one such problem, which is to find the K-th lexicographical string of all happy strings of length N, that can be solved using DFS and see whether this approach provides the most optimal solution or not.
Problem Statement
The question states that a happy string is a string that:
Consists of letters only of the set [‘A’, ‘B’, ‘C’]
No 2 consecutive letters are the same, i.e.,
S[i] != S[i+1] {1<= i <= S.length - 1}
You have been given 2 integers, N and K.
It means that you have to consider a list of all happy strings of length N sorted in the lexicographical order.
And you have to return the K-th string in this list.
Note- Return an empty string if the total number of happy strings of length N is less than K.
Constraints-
1 <= N <= 10
1 <= K <= 100
Example
N = 1
K = 3
List of happy strings = [‘A,’ ‘B,’ ‘C’]
The 3rd string is ‘C.’
2. N = 1
K = 5
List of happy strings = [‘A’, ‘B’, ‘C’]
Since there are only three happy strings of length 1, the answer is an empty string.
3. N = 3
K = 4
List of happy strings = [‘ABA’, ‘ABC’, ‘ACA’,’ ACB’]
The 4th string is ‘ACB.’
Brute Force
The brute force technique uses recursion to solve the problem. Since the input constraints state that N cannot exceed 10, we can simply use the DFS algorithm to produce the happy sequences.
When we call the DFS function recursively, we only push to the next character if it isn't the same as the previous. We know it's a happy string when we have the KthN-sized string.
Algorithm
We declare a vector, RESULT, of type string to store our resultant string.
Then we declare a variable, LAST, to check the last character of the current string.
Then we iterate through ‘a’, ‘b’, and ‘c’ and compare LAST with the current character of the iteration.
If they are the same, the value of the current character is incremented.
Else the recursive function is called once again.
The strings are stored in the vector, and the K-th one is returned.
Implementation
Program
// C++ program to find the K-th lexicographical string of all happy strings of length 'N.’
#include <iostream>
#include <vector>
using namespace std;
// Recursive function that will return the K-th happy string.
void dfs(vector<string> & result, string cur, int n)
{
// Base case.
if (cur.length() == n)
{
result.push_back(cur);
return;
}
// Storing the last character of the current string.
char last = (cur == "") ? ' ' : cur.back();
for (char x = 'a'; x <= 'c'; x++)
{
// If the current character and the last character are not the same, the recursive function is called again.
if (x != last)
{
dfs(result, cur + x, n);
}
}
}
// Function to find the K-th lexicographical string of all happy strings of length 'N'.
string getHappyString(int n, int k)
{
// The result vector will store our answer.
vector<string> result;
// Calling the recursive function dfs().
dfs(result, "", n);
// Returning our answer.
if (k <= result.size())
return result[k - 1];
// Empty string is returned if the value of 'K' is greater than the size of the vector.
return "";
}
int main()
{
int n, k;
// Taking user input.
cout << "Enter the length of the string (N), and the Kth number to be found: ";
cin >> n >> k;
// Calling the function to find the K-th lexicographical string of all happy strings of length 'N'.
cout << "The kth happy string of length N is: " << getHappyString(n, k);
return 0;
}
You can also try this code with Online C++ Compiler
Enter the length of the string, N, and the kth number to be found: 3 5
Output:
The kth happy string of length N is bab.
Complexity Analysis
Time Complexity
The time complexity is given by O(2N-1), where N is the length of the string.
For the first position of our happy string, we have 3 possibilities: it can contain any of the three letters A, B, or C. The rest of the letters in the string, now of length N - 1 have only 2 possibilities each. So the total number of permutations possible is 3 * 2N-1. Thus, the time complexity is O(2N-1).
Space Complexity
The space complexity is also given by O(2N-1), where N is the length of the string.
The height of the recursion stack is N, and 3 * 2N-1 strings are stored in the vector of strings.
So the space complexity is given by O(N +3 * 2N-1), which is equal to O(2N-1).
Optimal Solution
On carefully examining the case, we see that the happy strings follow a pattern that is quite similar to the increment of a binary number.
For example, if N = 3 and K = 5,
Algorithm
The total number of possible happy strings of length N is equal to 3 * 2N-1.
So if K is greater than this number, the answer will always be an empty string.
We initialise a variable PREV, to store the value of S[i - 1] . It is initially initilaised with ‘d’ else S[0] will not satisfy S[i] >= S[i - 1].
The current leftmost character is calculated using ‘a’ + K >> N.
If S[i] >= S[i-1], the value of S[i] is further incremented.
The K-th bit is discarded using ((1<<n)-1).
The pointer is incremented accordingly, and the process is repeated until we find our K-th string.
Implementation
Program
#include <iostream>
using namespace std;
// Function to find the K-th lexicographical string of all happy strings of length 'N.’
string getHappyString(int n, int k)
{
// Declaring our answer string.
char str[n + 1], *ans = str;
// If 'K' is greater than the total number of possible happy strings of length 'N', we return an empty string.
if (k > (3 << (n - 1)))
{
str[0] = '\0';
return ans;
}
// Decrementing 'K'.
k = k - 1;
// Variable 'PREV' is declared to hold S[i - 1].
// It is initialized as 'd' so that S[0] will NOT satisfy S[i] >= S[i-1].
char prev = 'd';
while (--n >= 0)
{
// The current leftmost character can be calculated by K >> N.
// S[i] (being pointed to by *ANS), can then be determined by 'a' + S[i].
// S[i] has to be further incremented if S[i] >= S[i - 1].
*ans = ('a' + (k >> n));
*ans += (*ans >= prev) ? 1 : 0;
// We can now throw away the leftmost bit by masking K with N - 1 bits of 1, which is ((1 << N) - 1).
k = k & ((1 << n) - 1);
// Updating 'PREV' and 'ANS'.
prev = *ans;
ans++;
}
*ans = '\0';
ans = str;
// Returning our result.
return ans;
}
int main()
{
int n, k;
// Taking user input.
cout << "Enter the length of the string, N, and the kth number to be found: ";
cin >> n >> k;
// Calling the function to find the K-th lexicographical string of all happy strings of length 'N'.
cout << "The k-th happy string of length N is " << getHappyString(n, k);
return 0;
}
You can also try this code with Online C++ Compiler
FIFO stands for First in First Out. It means that the element first inserted into the data structure is the first one to be processed. Example Queue
What type of Data Structure is a string?
A string is a Linear Data Structure.
Conclusion
So, this blog discussed the problem of the K-th Lexicographical String of All Happy Strings of Length N, using 2 different approaches, discussing each approach's time and space complexity.
To learn more, head over right now toCoding Ninjas Studio to practice problems on topics like Brute Force, DFS, and backtracking, and crack your interviews like a Ninja!
Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.
8+ registered 