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.
Brute Force
3.1.
Algorithm
3.2.
Implementation
3.2.1.
Program
3.2.2.
Input
3.2.3.
Output:
3.3.
Complexity Analysis
4.
Optimal Solution
4.1.
Algorithm
4.2.
Implementation
4.2.1.
Program
4.2.2.
Input
4.2.3.
Output
4.3.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is FIFO in Programming?
5.2.
What type of Data Structure is a string?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

The K-th Lexicographical String of All Happy Strings of Length ‘N’

Author Ishita Chawla
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM
DSA Problems

Introduction

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 givenintegers, 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 is less than K.

Constraints-

  • 1 <= N <= 10
  • 1 <= <= 100

Example

  1. 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.’

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

Brute Force

The brute force technique uses recursion to solve the problem. Since the input constraints state that 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 Kth N-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;
}

Input

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 is the length of the string.

For the first position of our happy string, we have 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-1Thus, the time complexity is O(2N-1).

Space Complexity

The space complexity is also given by O(2N-1), where 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,

illustration image

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

Input

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(N), where is the length of the string.

There is only one string of length N that we are constructing.

Space Complexity

The space complexity is given by O(1).

As we have not used extra space to store the strings, the space complexity is constant, i.e., O(1).

Also see, Euclid GCD Algorithm

Frequently Asked Questions

What is FIFO in Programming?

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 to Coding Ninjas Studio to practice problems on topics like Brute ForceDFS, 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.

Recommended problems -

 

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

In case of any comments or suggestions, feel free to post them in the comments section.

Previous article
Implement Hamiltonian Cycle
Next article
Determine the longest path from the source cell to the destination cell in a matrix
Live masterclass