LeetCode 1415: The k-th Lexicographical String of All Happy Strings of Length n

Explanation:

To solve this problem, we can generate all possible happy strings of length n in lexicographical order and return the k-th string. We can use backtracking to generate all possible happy strings. We start with an empty string and at each step, we try adding all possible characters 'a', 'b', 'c' to the current string as long as it doesn't violate the happy string condition.

Algorithmic Idea:

1. Start with an empty string and call a recursive function to generate all happy strings.
2. In the recursive function, for each character 'a', 'b', 'c', check if adding it to the current string violates the happy string condition. If not, continue recursively.
3. Keep track of the count of happy strings found and return the k-th string.

Time Complexity:

The time complexity of this approach is O(3^n) since at each step we have 3 choices to make.

Space Complexity:

The space complexity is O(n) for the recursive call stack.

:

class Solution {
    public String getHappyString(int n, int k) {
        List<String> result = new ArrayList<>();
        generateHappyStrings(n, new StringBuilder(), result);
        
        if (k > result.size()) {
            return "";
        }
        
        return result.get(k - 1);
    }
    
    private void generateHappyStrings(int n, StringBuilder current, List<String> result) {
        if (current.length() == n) {
            result.add(current.toString());
            return;
        }
        
        for (char c : new char[]{'a', 'b', 'c'}) {
            if (current.length() == 0 || current.charAt(current.length() - 1) != c) {
                current.append(c);
                generateHappyStrings(n, current, result);
                current.deleteCharAt(current.length() - 1);
            }
        }
    }
}