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

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Complete search

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:
		poss_per_group = 2 ** (n - 1)
		group_num = math.ceil(k / poss_per_group) - 1
		starting_char = ''
		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
			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:
		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:
		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()
		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