Scale Engineer

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

Med
#1309Time: `O(N * 3 * 2^(N-1))`, where N is the length of the string. We generate `3 * 2^(N-1)` strings, and each string creation/copy takes `O(N)` time.Space: `O(N * 3 * 2^(N-1))` to store all the generated happy strings. The recursion stack depth adds an additional `O(N)`.
Patterns
Backtracking
Data structures
String

Prompt

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.

 

Example 1:

Input: n = 1, k = 3
Output: "c"
Explanation: The list ["a", "b", "c"] contains all happy strings of length 1. The third string is "c".

Example 2:

Input: n = 1, k = 4
Output: ""
Explanation: There are only 3 happy strings of length 1.

Example 3:

Input: n = 3, k = 9
Output: "cab"
Explanation: There are 12 different happy string of length 3 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]. You will find the 9th string = "cab"

 

Constraints:

  • 1 <= n <= 10
  • 1 <= k <= 100

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating all possible happy strings of length n using recursion (backtracking). We store these strings in a list. Since the backtracking process explores characters in lexicographical order ('a', 'b', 'c'), the resulting list will also be sorted lexicographically. Finally, we check if the list has at least k strings and return the k-th one if it exists.

Algorithm

    1. Initialize an empty list happyStrings to store the results.
    1. Create a recursive helper function generate(n, current, list).
    1. In generate, if current.length() == n, add current.toString() to list and return.
    1. In generate, loop through characters 'a', 'b', 'c'.
    1. If the character can be appended (i.e., not same as the last character of current), append it, recurse, and then backtrack by removing it.
    1. Call the generate function with an initial empty string builder.
    1. After the function returns, check if k is within the bounds of happyStrings.size().
    1. If k <= happyStrings.size(), return happyStrings.get(k - 1). Otherwise, return "".

Walkthrough

We define a recursive function, say generate(currentString, n, list). The base case for the recursion is when the currentString reaches the desired length n. At this point, we add the generated string to our list of results. In the recursive step, we iterate through the characters 'a', 'b', 'c'. For each character, we check if it's different from the last character of the currentString. If it is (or if the string is empty), we append the character and make a recursive call. After the call returns, we backtrack by removing the character we just added. The initial calls to the function will be with an empty string, which then branches out for 'a', 'b', and 'c' as the first character. After the entire generation process is complete, we have a list of all happy strings, sorted. We then simply retrieve the element at index k-1. If k is larger than the number of strings found, we return an empty string.

class Solution {    public String getHappyString(int n, int k) {        List<String> happyStrings = new ArrayList<>();        generate(n, new StringBuilder(), happyStrings);                if (k > happyStrings.size()) {            return "";        }        return happyStrings.get(k - 1);    }     private void generate(int n, StringBuilder current, List<String> list) {        if (current.length() == n) {            list.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);                generate(n, current, list);                current.deleteCharAt(current.length() - 1); // backtrack            }        }    }}

Complexity

Time

`O(N * 3 * 2^(N-1))`, where N is the length of the string. We generate `3 * 2^(N-1)` strings, and each string creation/copy takes `O(N)` time.

Space

`O(N * 3 * 2^(N-1))` to store all the generated happy strings. The recursion stack depth adds an additional `O(N)`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly finds the k-th string by leveraging the natural lexicographical order of backtracking.

Cons

  • Highly inefficient as it generates all possible happy strings, regardless of the value of k.

  • Consumes a large amount of memory to store all the generated strings.

Solutions

public class Solution { public string GetHappyString ( int n , int k ) { List < string > ans = new List < string >(); StringBuilder s = new StringBuilder (); void Dfs () { if ( s . Length == n ) { ans . Add ( s . ToString ()); return ; } if ( ans . Count >= k ) { return ; } foreach ( char c in "abc" ) { if ( s . Length == 0 || s [ s . Length - 1 ] != c ) { s . Append ( c ); Dfs (); s . Length --; } } } Dfs (); return ans . Count < k ? "" : ans [ k - 1 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem