K-th Lexicographical String of All Happy Strings in C++

Suppose we have a string. We will call that a happy string when it consists of only ['a', 'b', 'c'] letters, and s[i] != s[i + 1] for all values of i from 1 to length of s - 1 (here the string is 1-indexed).

So, if we have two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order. We have to find the the kth string of this list or return an empty string if there are less than k happy strings of length n

So, if the input is like n = 3 and k = 9, then the output will be "cab", there are 12 different happy strings, these are ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"], the 9th one is "cab".

To solve this, we will follow these steps −

• Define an array ret

• Define a function solve(), this will take s, l initialize it with 1,

• if l is same as x, then −

  • insert s at the end of ret

  • return

• for initialize i := 0, when i < 3, update (increase i by 1), do −

  • if last element of s is not equal to c[i], then −

    • solve(s + c[i], l + 1)

• From the main method, do the following −

• x := n

• if n is same as 0, then −

  • return empty string

• solve("a")

• solve("b")

• solve("c")

• sort the array ret

• return (if k > size of ret, then blank string, otherwise ret[k - 1])

Example 

Let us see the following implementation to get a better understanding −

 Live Demo

#include <bits/stdc++.h>
using namespace std;
struct Cmp{
   bool operator()(string& a, string& b) {
      return !(a < b);
   }
};
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
   vector<string> ret;
   int x;
   void solve(string s, int l = 1){
      if (l == x) {
         ret.push_back(s);
         return;
      }
      for (int i = 0; i < 3; i++) {
         if (s.back() != c[i]) {
            solve(s + c[i], l + 1);
         }
      }
   }
   string getHappyString(int n, int k){
      x = n;
      if (n == 0)
         return "";
      solve("a");
      solve("b");
      solve("c");
      sort(ret.begin(), ret.end());
      return k > ret.size() ? "" : ret[k - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.getHappyString(3,9));
}

Input

3,9

Output

cab