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

MediumStringBacktracking
Leetcode Link

Problem Description

The problem requires us to define a "happy string" as a string that fulfills two conditions: (1) it is composed only of the characters 'a', 'b', and 'c', and (2) it does not have any consecutive identical characters. Examples of happy strings are "abc", "ac", and "b". The challenge is to generate a list of all possible happy strings of a specified length n, sort this list in lexicographical (dictionary) order, and then find the kth string in this sorted list. If the number of happy strings of length n is less than k, then we must return an empty string, indicating that the kth happy string does not exist.

Intuition

To solve the problem, the intuition is to use depth-first search (DFS) to generate all possible happy strings. DFS is effective here since it allows us to explore all possible character combinations for the strings of length n by appending one character at a time and only continuing from those combinations that remain happy (i.e., no consecutive characters are the same).

The key to the DFS approach is that once we've appended a character to the string, all subsequent choices must differ from the last character added. If we reach a length of n, that means we've constructed a valid happy string, which we then add to our list of answers.

We initiate DFS with an empty string and explore every possibility by adding 'a', 'b', or 'c', keeping in mind the last character we appended. We continue this process recursively until we either reach the string length n or there are no valid characters left to append.

Once we've generated all happy strings, we check if the total count is less than k. If it is, this means there is no kth happy string, and we should return an empty string. Otherwise, we return the string that is at the k-1 index in the list (as arrays are 0-indexed in Python, and our requirement is 1-indexed).

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used to implement priority queue?

Solution Approach

The solution uses a recursive Depth-First Search (DFS) algorithm to build up the "happy strings" one character at a time. Here’s how the solution works, breaking it down to the key components:

  • A helper function dfs(t) is defined to perform the DFS on the current string t. The core idea is to keep appending characters to t until it reaches the desired length n.
  • Within the dfs function, we first check if the length of t has reached n. If it has, we add t to the ans list. This signifies that we have successfully created a happy string of the required length.
  • For each recursive call to dfs, we iterate through the characters 'a', 'b', and 'c'. For each character c, if the last character of t (if t is not empty) is the same as c, we skip to the next iteration, as we cannot have repeating characters.
  • If the last character is not the same as c, or if t is empty, we make a recursive call to dfs with t + c, effectively probing this path in the search space.
  • The recursion continues until we either reach strings of length n or exhaust all possibilities of constructing a happy string from the current substring.
  • The ans list is a data structure used to store all the happy strings we discover while performing DFS. It is declared outside the dfs function to retain its value across multiple recursive calls.
  • Once the DFS is complete, we look at the ans list. If the length of ans is less than k, implying there aren't enough happy strings, we return an empty string. Otherwise, we return the k-1th string in the list, since lists in Python have zero-based indexing.

The DFS approach is efficient for this problem because it systematically explores all valid combinations without constructing invalid strings. The solution is also space-optimized since it only saves the valid happy strings found and does not store any intermediate invalid states.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach where n = 3 and k = 5. We are to generate all possible happy strings of length 3 and find the 5th string in lexicographical order.

  1. We start with an empty string, t, and initiate our recursive dfs(t) function.
  2. In the first level of the recursive tree, we have three choices for the first character: 'a', 'b', or 'c'. Let's start with t = "a".
  3. For the second character, we have two choices ('b' or 'c') since it can't be identical to the last character 'a'. We thus explore t = "ab" and t = "ac".
  4. Assuming we now have t = "ab", for the third character we again have two choices ('a' or 'c'). This yields t = "aba" and t = "abc".
  5. We repeat the same process starting from t = "ac" and get t = "aca" and t = "acb". Since we are building up in lexicographical order, we can see that "abc" comes before "acb". Therefore, "acb" will be considered later.
  6. Continuing this process, starting with t = "b" and then t = "c", and ensuring no consecutive characters are the same, we construct the following strings: ["aba", "abc", "aca", "acb", "bac", "bca", "cab", "cba"].
  7. We have generated all possible happy strings of length 3. Now we sort them (although they were constructed in sorted order due to our approach): ["aba", "abc", "aca", "acb", "bac", "bca", "cab", "cba"].
  8. To find the k = 5th string, we look at index k-1 = 4 in the list (as the indexing starts from 0), which gives us "bac".

Here, the 5th happy string of length 3 in lexicographical order is "bac". If the value of k had been greater than the number of happy strings generated, our function would return an empty string, indicating that there's no valid answer.

Solution Implementation

1class Solution:
2    def getHappyString(self, length: int, index: int) -> str:
3        # Helper function for depth-first search to find all happy strings
4        def dfs(current_str):
5            # Base condition: if current string reaches the desired length, add to results
6            if len(current_str) == length:
7                happy_strings.append(current_str)
8                return
9            # Iterate through all possible characters
10            for char in 'abc':
11                # Avoid repeating characters
12                if current_str and current_str[-1] == char:
13                    continue
14                # Recursively build the string
15                dfs(current_str + char)
16
17        # List to store all possible happy strings
18        happy_strings = []
19        # Start the DFS with an empty string
20        dfs('')
21        # If there are fewer than k happy strings, return an empty string
22        # Otherwise, return the k-th happy string (1-indexed)
23        return '' if len(happy_strings) < index else happy_strings[index - 1]
24
25# The code has been rewritten using Python 3 syntax.
26# Variable names have been standardized for clarity, following Python naming conventions.
27# Comments in English have been added to explain the intent of the code.
28
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    // List to hold all happy strings
6    private List<String> happyStrings = new ArrayList<>();
7
8    // Function to return the kth happy string of length n
9    public String getHappyString(int n, int k) {
10        // Generate all happy strings of length n
11        generateHappyStrings("", n);
12        // If the list size is less than k, no such k-th happy string exists. Return an empty string.
13        return happyStrings.size() < k ? "" : happyStrings.get(k - 1);
14    }
15
16    // Helper function to generate happy strings using Depth First Search (DFS)
17    private void generateHappyStrings(String current, int n) {
18        // If the current string's length is n, add it to the list of happy strings
19        if (current.length() == n) {
20            happyStrings.add(current);
21            return;
22        }
23      
24        // Loop through the characters 'a', 'b', and 'c'
25        for (char c : "abc".toCharArray()) {
26            // If the last character of the current string is the same as 'c', skip to the next iteration
27            // to ensure we do not have consecutive same characters, which makes the string unhappy
28            if (current.length() > 0 && current.charAt(current.length() - 1) == c) {
29                continue;
30            }
31            // Otherwise, add 'c' to current and continue to search for the rest of the string
32            generateHappyStrings(current + c, n);
33        }
34    }
35}
36
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Vector to store the valid "happy strings".
7    std::vector<std::string> happyStrings;
8
9    // Main function to return the k-th happy string of length n.
10    // If there aren't k happy strings, an empty string is returned.
11    std::string getHappyString(int length, int k) {
12        // Initiate a depth-first search to generate all happy strings of length 'n'
13        generateHappyStrings("", length);
14        // Check if there are less than 'k' happy strings, return "" if true.
15        // Otherwise, return the k-th string (0-indexed, so we use k-1).
16        return happyStrings.size() < k ? "" : happyStrings[k - 1];
17    }
18
19private:
20    // Helper function to generate happy strings using DFS.
21    void generateHappyStrings(std::string current, int length) {
22        // If the current string has reached the target length 'n',
23        // add it to the list of happy strings and return.
24        if (current.size() == length) {
25            happyStrings.push_back(current);
26            return;
27        }
28        // Iterate over each character from 'a' to 'c'.
29        for (char nextChar = 'a'; nextChar <= 'c'; ++nextChar) {
30            // If the last character is the same as the next character,
31            // skip to maintain the "happy" property.
32            if (!current.empty() && current.back() == nextChar) continue;
33            // Append the new character and continue the search.
34            current.push_back(nextChar);
35            generateHappyStrings(current, length);
36            // Backtrack by removing the last character added.
37            current.pop_back();
38        }
39    }
40};
41
1// Array to store the valid "happy strings".
2let happyStrings: string[] = [];
3
4// Main function to return the k-th happy string of length n.
5// If there aren't k happy strings, an empty string is returned.
6function getHappyString(length: number, k: number): string {
7    // Initiate a depth-first search to generate all happy strings of the given length
8    generateHappyStrings("", length);
9    // Check if there are fewer happy strings than k, return an empty string if so.
10    // Otherwise, return the k-th string (0-indexed, so we use k-1).
11    return happyStrings.length < k ? "" : happyStrings[k - 1];
12}
13
14// Helper function to generate happy strings using DFS.
15function generateHappyStrings(current: string, length: number) {
16    // If the current string has reached the target length,
17    // add it to the list of happy strings and return.
18    if (current.length === length) {
19        happyStrings.push(current);
20        return;
21    }
22    // Iterate over each character from 'a' to 'c'.
23    for (let nextChar = 'a'.charCodeAt(0); nextChar <= 'c'.charCodeAt(0); nextChar++) {
24        let nextCharStr = String.fromCharCode(nextChar);
25        // If the last character is the same as the next character,
26        // skip to maintain the "happy" property.
27        if (current !== "" && current[current.length - 1] === nextCharStr) continue;
28        // Append the new character and continue the search.
29        generateHappyStrings(current + nextCharStr, length);
30        // No need to backtrack explicitly since strings are immutable in JavaScript/TypeScript,
31        // and each recursive call gets its own copy of the current string.
32    }
33}
34
35// Use the functions in your code:
36let length = 5; // The desired length for happy strings
37let k = 3;      // The position of the happy string to return
38let happyString = getHappyString(length, k); // Function call
39console.log(happyString); // Log the result
40
Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Time and Space Complexity

The provided Python code defines a class Solution with a method getHappyString that generates the k-th lexicographically smallest "happy" string of length n. A "happy" string is one in which no two adjacent characters are the same.

Time Complexity

The time complexity of the code is O(3^n).

Here's why:

  • The algorithm uses a depth-first search (DFS) to generate all possible "happy" strings of length n.
  • At each step of the DFS, there are at maximum 3 different characters ('a', 'b', 'c') that you can choose from, minus any character that is the same as the last character of the current string (t).
  • In the worst case, the DFS would generate all possible "happy" strings, and since each position can have 2 choices (after the first character), the number of possibilities is 3 * 2^(n-1), which simplifies to 3 * 2 * 2 * ... * 2 (with n-1 two's in the multiplication), which is O(3 * 2^(n-1)) = O(3^n).

Space Complexity

The space complexity of the code is O(3^n + n).

Here's why:

  • O(3^n) is for storing the ans list, which in the worst case might contain all possible "happy" strings.
  • O(n) is for the recursion stack depth, which goes as deep as n because we're generating strings of length n.
  • The space used by the ans list is the dominating factor, hence the space complexity is mainly dictated by the number of happy strings generated.

In summary, the brute-force DFS approach used in this code might be feasible for small n, but is impractical for large n due to its exponential time and space complexity.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫