aboutsummaryrefslogtreecommitdiff
path: root/kth_lex_str_happy_n.py
blob: 2eb9c5fdc0bdc5a15ce65f034f09a06a76a14351 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 1415. The k-th Lexicographical String of All Happy Strings of Length n

"""
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'. given
two integers 'n' and 'k', consider a list of all happy strings of length 'n'
sorted in lexicographical order. return the k'th string of this list or
return an empty string if there are less than 'k' strings of length 'n'.
"""


class Solution(object):
    def getHappyString(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        m = n

        def dfs(prefix, n, k):
            if n == 0:
                return prefix
            for c in "abc":
                if prefix and c == prefix[-1]:
                    continue
                cnt = 2 ** (m - len(prefix) - 1)
                if cnt >= k:
                    return dfs(prefix + c, n - 1, k)
                else:
                    k -= cnt
            return ""

        return dfs("", n, k)


if __name__ == "__main__":
    obj = Solution()
    print(obj.getHappyString(1, 3))
    print(obj.getHappyString(1, 4))
    print(obj.getHappyString(3, 9))