aboutsummaryrefslogtreecommitdiff
path: root/kth_lex_str_happy_n.c
blob: 21178ea955ce395d6b1acaea2c3949531ffcace2 (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
#include "leetcode.h"

/*
 * 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'.
 */

char *dfs(char *prefix, int n, int m, int *k) {
  if (!n)
    return prefix;
  for (char c = 'a'; c <= 'c'; c++) {
    int n = strlen(prefix);
    if (n && c == prefix[n - 1])
      continue;
    int cnt = (int)pow(2, m - n - 1);
    if (cnt >= *k) {
      prefix[n] = c;
      prefix[n + 1] = '\0';
      return dfs(prefix, n - 1, m, k);
    } else
      *k -= cnt;
  }
  return "";
}

char *getHappyString(int n, int k) {
  int m = n;
  char *prefix = (char *)malloc((n + 1) * sizeof(char));
  prefix[0] = '\0';
  return dfs(prefix, n, m, &k);
}

int main() {
  printf("%s\n", getHappyString(1, 3)); // expect: c
  printf("%s\n", getHappyString(1, 4)); // expect: null
  printf("%s\n", getHappyString(3, 9)); // expect: cab
}