[LeetCode] 1415. The k-th Lexicographical String of All Happy Strings of Length n

https://leetcode.com/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/description/

leetcode - The k-th Lexicographical String of All Happy Strings of Length n

문제 유형: 백트래킹, 수학, 조합론, 해 구성하기

문제 난이도: Medium

 

문제

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.

 

행복한 문자열은 'a', 'b', 'c'로만 이루어지고, 인접한 글자들간의 문자가 서로 다른 문자열을 말합니다.

두 정수 n과 k가 주어집니다. 길이가 n인, 사전순 오름차순 기준으로 k번째 행복한 문자열을 반환하시오.

 

풀이

백트래킹을 이용하면, 쉽게 생성해낼 수 있다.

모든 경우의 수들을 그리디하게 왼쪽우선으로 만들어서 k번째걸 반환하거나, 유효한 문자열을 만드는데 성공해서 k의 카운트를 낮추고 0이 된 그 문자열이 정답이 되게 하면 된다.

 

재귀로는 너무 쉬우니, 비재귀로도 풀어보자.

처음에는 3가지, 그 이후에는 2가지의 케이스로 갈라진다.

즉, 모든 만드는 경우는 3 * 2* (n-1)이다.

각 브랜치 'a', 'b', 'c'부터 시작하는 경우는 각각 2*(n-1)개 있다. 이를 block개 라고 하자.

만약 처음의 k가 block보다 작거나 같다면, 첫 글자는 'a'이다.

만약 처음의 k가 block보다는 크지만 2*block보다 작다면, 첫 글자는 'b'이다. 여기서 k에 block만큼 이미 빼주자.

만약 처음의 k가 2*block보다는 크지만 3*block보다 작다면, 첫 글자는 'c'이다. 여기서 k에 2*block만큼 빼주자. 

 

이제, 하위 브랜치로 내려가는 것은, 이진이고, 반복 가능하다. 아래 과정을 n-1번 반복할 것이다.

하위 브랜치의 경우의 수인 새로운 block은 2*(n-i-1)이다.

만약 남은 k가 block보다 작거나 같으면, 왼쪽 브랜치로 간다.

그렇지 않으면, 오른쪽 브랜치로 간다. 역시 k에 block만큼 빼준다.

이전에 어떤 알파벳을 추가했느냐에 따라 차이를 주면 되고, 그 이전 삽입한 알파벳도 업데이트해준다.

 

최종적으로 생성된 문자열을 리턴한다.

k에 block만큼 빼는 것은, 오프셋을 제거해서 하위 서브트리에 대해서만 고려한다는 의미로 보면 된다.

 

코드

C++(비재귀 풀이)

class Solution {
public:
    string getHappyString(int n, int k) {
        long long total = 3LL * (1LL << (n - 1));
        if(k > total) return "";
        
        string ans;
        long long blockSize = 1LL << (n - 1);
        char first;
        if(k <= blockSize) {
            first = 'a';
        } else if(k <= 2 * blockSize) {
            first = 'b';
            k -= blockSize;
        } else {
            first = 'c';
            k -= 2 * blockSize;
        }
        ans.push_back(first);
        
        char prev = first;
        for (int i = 1; i < n; i++) {
            long long block = 1LL << (n - i - 1);
            vector<char> options;
            for (char c : {'a', 'b', 'c'}) {
                if (c != prev) {
                    options.push_back(c);
                }
            }
            if(k <= block) {
                ans.push_back(options[0]);
                prev = options[0];
            } else {
                ans.push_back(options[1]);
                prev = options[1];
                k -= block;
            }
        }
        return ans;
    }
};

 

Go(재귀 풀이)

var (
    l int
    kk int
    ans string
)

func dfs(s string) bool {
    if len(s) == l {
        kk--
        if kk == 0 {
            ans = s
            return true
        }
        return false
    }

    ch := s[len(s)-1]
    if ch == 'a' {
        if dfs(s + "b") || dfs(s + "c") {
            return true
        }
    } else if ch == 'b' {
        if dfs(s + "a") || dfs(s + "c") {
            return true
        }
    } else {
        if dfs(s + "a") || dfs(s + "b") {
            return true
        }
    }
    return false
}

func getHappyString(n int, k int) string {
    l = n
    kk = k
    if dfs("a") || dfs("b") || dfs("c") {
        return ans
    }
    return ""
}