A happy string is a string that:

consists only of letters of the set ['a', 'b', 'c'].
s[i] != s[i + 1] for all values of i from 1 to s.length - 1 (string is 1-indexed).

For example, strings "abc", "ac", "b" and "abcbabcbcb" are all happy strings and strings "aa", "baa" and "ababbc" are not happy strings.
Given two integers n and k, consider a list of all happy strings of length n sorted in lexicographical order.
Return the kth string of this list or return an empty string if there are less than k happy strings of length n.
 
Example 1:
Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".

Example 2:
Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.

Example 3:
Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab"

Example 4:
Input: n = 2, k = 7
Output: ""

Example 5:
Input: n = 10, k = 100
Output: "abacbabacb"

 
Constraints:

1 <= n <= 10
1 <= k <= 100

Difficulty: interview

Starter code:

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        

Solutions:
import math

class Solution:
    def __init__(self):
        self.happy_string = ''
    
    def getHappyString(self, n: int, k: int) -> str:
        # determine starting character
        poss_per_group = 2 ** (n - 1)
        group_num = math.ceil(k / poss_per_group) - 1
        starting_char = ''
        
        # check to make sure there are at least k happy strings
        if k > poss_per_group * 3:
            return ''
        
        if group_num == 0:
            self.happy_string += 'a'
        elif group_num == 1:
            self.happy_string += 'b'
        else:
            self.happy_string += 'c'
            
        self.findNextChar(group_num, n - 1, group_num * poss_per_group, (group_num + 1) * poss_per_group, k)
        return self.happy_string
        
    def findNextChar(self, char_index: int, n: int, start: int, end: int, k: int) -> None:
        if n != 0:
            lower_index = -1
            upper_index = -1
            
            # 0 = 'a', 1 = 'b', 2 = 'c'
            if char_index == 0:
                lower_index = 1
                upper_index = 2
            elif char_index == 1:
                lower_index = 0
                upper_index = 2
            else:
                lower_index = 0
                upper_index = 1
                
            midpoint = int((start + end ) / 2)
            if (k <= midpoint):
                self.happy_string += self.indexToStr(lower_index)
                self.findNextChar(lower_index, n - 1, start, midpoint, k)
            else:
                self.happy_string += self.indexToStr(upper_index)
                self.findNextChar(upper_index, n - 1, midpoint, end, k)                
                
    def indexToStr(self, index: int) -> str:
        if index == 0:
            return 'a'
        elif index == 1:
            return 'b'
        else:
            return 'c'
                
            
            
        
            


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        m_vals = 3 * (2 ** (n - 1))
        if k > m_vals:
            return ''
        k -= 1
        m_vals //= 3
        vals = ['a', 'b', 'c']
        mapping = {0:'a',1:'b',2:'c'}
        s = mapping[k // m_vals]
        k %= m_vals
        m_vals //= 2
        prev_map = {'a':{0:'b',1:'c'},'b':{0:'a',1:'c'},'c':{0:'a',1:'b'}}
        while m_vals:
            mapping = prev_map[s[-1]]
            s += mapping[k // m_vals]
            k %= m_vals
            m_vals //= 2
        return s

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        cnt = 0
        choice = ['a','b','c']
        ret = []
        def backTrack(lastCh, idx, l):
            nonlocal cnt, ret
            if idx == n:
                cnt += 1
                if cnt == k:
                    ret = l
                    return True
                return False
            for ch in choice:
                if ch == lastCh:
                    continue
                l.append(ch)
                if backTrack(ch, idx+1, l):
                    return True
                l.pop()               
        backTrack('x', 0, [])
        return ''.join(ret)


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        nextLetter = {'a':'bc','b':'ac','c':'ab'}
        q = deque(['a','b','c'])
        while len(q[0]) != n:
            u = q.popleft()
            for v in nextLetter[u[-1]]:
                q.append(u + v)
        return q[k - 1] if len(q) >= k else '' 

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        nextLetter = {'a':'bc','b':'ac','c':'ab'}
        q = deque(['a','b','c'])
        while len(q[0]) != n:
            u = q.popleft()
            
            for v in nextLetter[u[-1]]:
                q.append(u + v)
        return q[k - 1] if len(q) >= k else ''

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        nextLetter = {'a': 'bc', 'b': 'ac', 'c': 'ab'} 
        q = collections.deque(['a', 'b', 'c'])
        while len(q[0]) != n:
            u = q.popleft()    
            for v in nextLetter[u[-1]]:
                q.append(u + v)
        return q[k - 1] if len(q) >= k else ''   

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        nextLetter = {'a': 'bc', 'b': 'ac', 'c': 'ab'} 
        q = collections.deque(['a', 'b', 'c'])
        while len(q[0]) != n:
            u = q.popleft()    
            for v in nextLetter[u[-1]]:
                q.append(u + v)
        return q[k - 1] if len(q) >= k else ''     


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        N = 3 << (n - 1)
        res = ''
        if k > N:
            return res
        k -= 1
        letters = ('a', 'b', 'c')
        res += letters[k * 3 // N]
        N //= 3
        k %= N
        for i in range(1, n):
            prev = res[i - 1]
            index = k * 2 // N
            offset = int(prev <= letters[index])
            res += letters[index + offset]
            N >>= 1
            k %= N
        return res


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        def stringformer(sts,prev):
            if len(sts) == n:
                l.append(sts)
                return 
            for i in ['a','b','c']:
                if i != prev:
                    stringformer(sts+i,i)
        
        l = []
        stringformer('','')
        if len(l) == 0 or (k>len(l)):
            return ''
        else:
            return l[k-1]


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        res= []
        s='abc'
        def dfs(n, res, path):
            if n==0:
                res.append(path)
                return
            for i in s:
                if not (path and path[-1]==i):
                    dfs(n-1, res, path+i)
        dfs(n, res, '')
        res.sort()
        return res[k-1] if k<=len(res) else ''


        
        



class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        res= []
        s='abc'
        def dfs(n, res, path):
            if n==0:
                res.append(path)
                return
            for i in s:
                if not (path and path[-1]==i):
                    dfs(n-1, res, path+i)
        dfs(n, res, '')
        #res.sort()
        return res[k-1] if k<=len(res) else ''


        
        



class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        if k > 3 * 1 << (n - 1):
            return ''
        other = [(1, 2), (0, 2), (0, 1)]
        ans = [(k-1) // (1 << (n - 1))]
        k2bit = bin((k-1) % (1 << (n - 1)))[2:]
        k2bit = '0'*(n-1-len(k2bit)) + k2bit
        
        for i in range(1, n):
            ans.append(other[ans[i-1]][int(k2bit[i-1])])
        letters = 'abc'

        return ''.join([letters[x] for x in ans])


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        
        def rec(x,n,s):
            
            if len(x) == n:
                r.append(x)
            else:
                for i in range(len(s)):
                    if s[i] == 'a':
                        rec(x+s[i],n,'bc')
                    elif s[i] == 'b':
                        rec(x+s[i],n,'ac')
                    else:
                        rec(x+s[i],n,'ab')
    
                    
        r = []
        rec('',n,'abc')
        
        if k<=len(r):
            return r[k-1]
        else:
            return ''

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        
        def dfs(ind,nlen,path,res):
            if ind == nlen:
                res.append(path)
                return
            for i in range(3):
                if len(path)==0 or (path[-1]!=ls[i]):
                    dfs(ind+1,nlen,path+ls[i],res)
        
        ls = ['a','b','c']
        vis = [0]*3
        res = []
        dfs(0,n,'',res)
        res.sort()
        if len(res)<k:
            return ''
        return res[k-1]


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        s, res = 'abc', []
        
        def dfs(s, length, path, res):
            if len(path) == length:
                res.append(path)
                return
            for i in range(len(s)):
                if path and s[i] == path[-1]: continue
                else: dfs(s, length, path + s[i], res)
        
        dfs(s, n, '', res)
        res.sort()
        # print(res)
        return res[k - 1] if k <= len(res) else ''

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        
        self.result = ['']
        self.index = 0
        def back_track(cur):
            if len(cur) == n:
                self.index+=1
                if self.index == k: 
                    self.result[0] = cur
                return
            for i in range(ord('a'), ord('d')):
                if len(cur)>0 and cur[-1]== chr(i):
                    continue
                back_track(cur+chr(i))
            return 
        back_track('')
        return self.result[0]
            
            


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        res=[]
        
        def helper(cur,tmp):
            if len(cur)==n:
                res.append(cur)
                return             
            for t in tmp:
                new=[i for i in ['a','b','c'] if i!=t]
                helper(cur+t,new)
            
        helper('',['a','b','c'])
        return res[k-1] if k-1<len(res) else ''

from collections import deque

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        chars = ['a', 'b', 'c']
        queue = deque()
        queue.extend(chars)

        last_length = 0
        length_count = 0
        while len(queue[0]) <= n:
            string = queue.popleft()
            if len(string) != last_length:
                last_length = len(string)
                length_count = 1
            else:
                length_count += 1

            if n == last_length and k == length_count:
                return string

            for char in chars:
                if char != string[-1]:
                    queue.append(string + char)

        return ''


import math

LETTER_SET = ['a', 'b', 'c']
LEFT = 0
RIGHT = 1
    

class Solution:

    def getHappyString(self, n: int, k: int) -> str:
        index = self.getRootIndex(n, k)
        if index == None: return ''
        kth_happy = LETTER_SET[index]
        
        happy_strings_per_node = self.calculateTotalNumOfHappyForN(n)
        min_range = happy_strings_per_node * index + 1
        max_range = happy_strings_per_node * (index + 1)
        for level in range(n-1):
            direction = self.findDirection(min_range, max_range, k)
            kth_happy = self.nextHappyString(kth_happy, direction)
            min_range, max_range = self.fetchNewRange(min_range, max_range, direction)
            
        return kth_happy
        
    def findDirection(self, min_range, max_range, k):
        min_low = min_range
        min_high = math.floor((min_range + max_range) / 2)
        max_low = min_high + 1
        max_high = max_range
        is_in_min_range = k >= min_low and k <= min_high
        return LEFT if is_in_min_range else RIGHT
        
    def fetchNewRange(self, min_range, max_range, direction):
        min_low = min_range
        min_high = math.floor((min_range + max_range) / 2)
        max_low = min_high + 1
        max_high = max_range

        return (min_low, min_high) if (LEFT == direction) else (max_low, max_high)             
    
    def calculateTotalNumOfHappyForN(self, n):
        return 2**(n-1)
    
    def getRootIndex(self, n, k):
        happy_strings_total = self.calculateTotalNumOfHappyForN(n) * len(LETTER_SET)
        happy_strings_per_node = happy_strings_total / len(LETTER_SET)
        
        for i in range(len(LETTER_SET)):
            min_range = happy_strings_per_node * i + 1
            max_range = happy_strings_per_node * (i + 1)
            
            if k >= min_range and k <= max_range:
                return i
            
        return None
    
    def nextHappyString(self, string, direction):
        happyStrings = []
        for letter in LETTER_SET:
            if self.isValidHappyString(string, letter):
                happyStrings.append(string + letter)
        return happyStrings[direction]
    
    def isValidHappyString(self, string, letter):
        return string[-1] != letter

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        s=''
        l=['a','b','c']
        self.count=0
        self.res=''
        def alls(n,s,k):
            for i in l:
                if(len(s)!=0):
                    if(s[-1]==i):
                        continue
                if(n==0):
                    self.count+=1
                    if(self.count==k):
                        self.res=s
                        return self.res
                    break
                n-=1
                s+=i
                alls(n,s,k)
                n+=1
                s=s[:-1]
            return self.res
        return alls(n,s,k)

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        k = k -1
        
        def dfs(path, new):
            
            if len(path) == n:
                res.append(path)
                return
            
            
            if len(path) == 0:
                for ind, x in enumerate(new):
                    dfs(path+x, new[:ind] + new[ind+1:])
            
            
            else:
                last = path[-1]
                l = []
                for i in letters:
                    if i != last:
                        l.append(i)
                
                for ind, x in enumerate(l):
                    dfs(path+x, l[:ind] + l[ind+1:])
        
        
        
        
        
        letters = ['a', 'b', 'c']
        res =[]
        dfs('', letters)
        
        if k >= len(res):
            return ''
        else:
            return res[k]

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        if n==1:
            if k<4:
                return ['a','b','c'][k-1]
            else:
                return ''
        ordered=[]
        def is_valid(s):
            if s[len(s)-1]==s[len(s)-2]:
                return False
            return True
        queue=['a','b','c']
        j=0
        while queue:
            if len(queue[len(queue)-1])==n+1:
                break
            element=queue.pop(0)
            for char in ['a','b','c']:
                if is_valid(element+char):
                    if len(element+char)==n:
                        ordered.append(element+char)
                    queue.append(element+char)
        if k>len(ordered):
            return ''
        return ordered[k-1]

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        results = []
        letters = 'abc' 
        combos = set()
        def backtrack(s):
            nonlocal results 
            if len(results) == k: 
                return 
            if len(s) == n and s not in combos:
                combos.add(s)
                results.append(s)
                return
            for i in range(0, len(letters)):
                if s and s[-1] == letters[i]:
                    continue
                s += letters[i] 
                backtrack(s)
                s = s[0:-1]
                
        backtrack('')
        return results[-1] if len(results) == k else ''


class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        count = [0]
        letters = ['a','b','c']
        def bt(cur_list=[],last_appended = ''):
            if len(cur_list) == n:
                count[0]+=1
                if count[0] == k:
                    return ''.join(cur_list)
                else:
                    return ''
            for i in letters:
                if i == last_appended:
                    continue
                else:
                    cur_list.append(i)
                    output = bt(cur_list,i)
                    if output !='':
                        return output
                    cur_list.pop()
            return ''
                    
            
        output = bt()
        return '' if not output else output