1415.

class Solution:
    def backtrack(self, n, k, partial):
        # Base Case
        # If I have generated a string of the correct length
        # do not proceed any longer.
        if len(partial) == n:
            self.counter += 1
            
            # If I have found the 'k'th happy string, Return this to the main caller.
            if self.counter == k:
                return partial
            return None
        
        # I have a partial solution that isn't fully built up.
        # Try a/b/c in order
        for char in ('a', 'b', 'c'):
            # Bounding Function
            # Don't have duplicate letters in a row.
            if len(partial) != 0 and char == partial[-1]:
                continue
            
            kthHappyString = self.backtrack(n, k, partial + char)
            if kthHappyString:
                return kthHappyString
        return None
            
    def getHappyString(self, n: int, k: int) -> str:
        '''
        Input:
            n - length of string
            k - get the 'k'th happy string
        Constraint:
            Happy string only has letters {a,b,c}
            No same letters in a row. (s[i] != s[i + 1])
        Example:
            n = 1, k = 3
            [a,b,c] --> c
        Approach:
            Do DFS until I reach a subset with 'n' entries.
            If this is the 'k'th entry, then return this.
        '''
        self.counter = 0
        happyString = self.backtrack(n, k, '')
        return happyString if happyString != None else ''