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

You can find the kth happy string of length n by using a recursive approach to generate the strings and keeping track of the count.

Here’s a Python function to do that:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        def generateHappyStrings(prefix):
            if len(prefix) == n:
                happy_strings.append(prefix)
                return

            for char in 'abc':
                if not prefix or char != prefix[-1]:
                    generateHappyStrings(prefix + char)

        happy_strings = []
        generateHappyStrings("")

        if k > len(happy_strings):
            return ""

        return happy_strings[k - 1]

This code defines a recursive function, generateHappyStrings, to generate all happy strings of length n. It then checks whether k is within the bounds of the generated happy strings and returns the kth string if it is, or an empty string if it’s not.

For example, with n = 3 and k = 9, this code would return "cab".

title: The k-th Lexicographical String of All Happy Strings tags: dfs backtracking

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"

Example 4:
Input: n = 2, k = 7
Output: ""

Example 5:
Input: n = 10, k = 100
Output: "abacbabacb"

Constraints

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

Thinking Process

Define the Term

What does lexicographical string mean?
What does lexicographical ordering mean?

Backtracking is a type of traversal. Can you use that fact to take care of the order? Ask: Can you give me an example? When an abstract statement does not make sense to you.

Visual Model of the Problem

Draw the decision tree diagram. We now know that we don’t have to do any comparison to order them.

Define the Interface

Input 

n - the length of a happy string
k - return the kth item

Output

The kth happy string of length n.

Constraints

Some of the constraints may be implemented as bounding functions.

No subsequent letters in a row Only choose letters from {a,b,c}

Outline Solution

Available choices are a, b and c.
Are we going to have a bounding function?
Check for duplicates.

Approach

Choices: Iterate through (a, b, c) on every level. We don’t use index and index + 1

Bounding Function

If i != 0 and partial[i] == partial[i - 1] Prune Goal If length of partial result == n result.append(partial) Two options Build all the results and return the nth result Use a counter and return the partial (no need to build up the intermediate results)

If length of partial result == n If counter == k Return partial result.append(partial)

If using goal 2, return result[k-1]

Create a wrapper method that provides initial values to the get happy string method. The goal is expressed as checking if the partial result is n and the counter is k. If so, return the partial.

Partials can be of length 0, 1 or 2. How are we pruning the tree? Use the example to see when the counter must be incremented and we return the result. We build the partial as we go down the decision tree. Add comments to separate sections of code that are focused on a single task.

Goal Code goes here Choices Code goes here Bounding Function Code goes here

The for loop iterates through all the choices, in this case a,b,c. If i < n and add print statement all variables in the beginning of the recursive method. The index i is not getting incremented, we are getting into an infinite recursion, a is getting added unlimited amount of time.

Bounding function prunes the recursion tree

Demystifying Computational Thinking by Valerie J Shute

The counter is incremented only in the local copy of the recursive call. It’s a method inside a method in Python. The unchoose step was missing.

Base case: check if the length of the partial is equal to n. Append the solution to the result. There is no need to append it to the result, check if k is hit, if so return the partial as the result.

Make variables immutable if you can. This prevents bugs from occurring. String is immutable in Python. Array is mutable. Array append will create more arrays.

Terminate the algorithm early if we don’t need to do any more work. This improves performance. We don’t need to compute from k+1 to n.

Problem Definition

Define the Terms

Happy String: consists only of letters of the set `[‘a’, ‘b’, ‘c’]
String: s[i] != s[i + 1] for all values of i from 1 to s.length - 1
Lexicographical order: alphabetical order

Define the Interface

Input: n, k (integers) Output: string

Identify Implicit Inputs

Set of characters: a, b, c

Define the Goal

Return the kth string of this list or return an empty string if there are less than k happy strings of length n.

Identify the Constraints

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

Determine the Scope

List assumptions
Define boundaries of the problem

Search the Problem Space

Look for clues in the problem statement

Classify the Problem

By drawing the decision tree, we recognize this as a recursive backtracking algorithm. This is a variation of the Generate Permutations problem.

Decontextualize the Problem
Can you think of this problem in a different way?
Can you reframe it?

Problem Representation

Analyze the Input and Output

n decides the output string length
k decides the index of the character in the implicit input array:  ["a", "b", "c"]

Analyze the Examples

Example 1: We grab the third element in the set.
Example 2: We go out of bounds, so we return empty string.
Example 3: We need to generate all the permutations of the input set of characters that are happy strings and find the kth permutation. The permutations are in alphabetical order. We can probably generate only k happy strings.
Example 4: ["ab", "ac", "ba", "bc", "ca", "cb"]
Example 5: Assume by induction, it will work.
Example 6: ["ab", "ac", "ba", "bc", "ca", "cb"], k = 6

Decrement k when we reach the leaf node. We start with n = 1, n = 2, n = 3 … n = 10. We have 12 happy strings for a (a, b, c).

Consider the Simple Cases First
Find missing cases
Find edge cases

Solve the Problem by Hand

Done

Recognize the Pattern

Describe the Pattern
Distill the Observations into Insights

We only need to generate up to k happy strings.

Identify the Invariants

Generate happy string length cannot exceed n.

Recursive Approach

Base Case: n = 1, no need to generate any happy strings just return the kth happy string from the implicit input.

Base Case #2: How do we restrict the size of the generated happy string? When the size of the happy string reaches the value of n. Two ways:

We can add the value to an array.
We can use k as a counter by decrementing at each recursive call, when it reaches 0, we will return the generated happy string. We use less space.

We need a bounding function to enforce that the adjacent characters have to be different. What will the bounding function look like? We don’t need a bounding function in this case. Have a parent character and the current character, if they are the same, we skip it. Choose the next available character.

Unit of Work is done before the recursive call. I need to choose a character from the set and append it to the happy string.

The options are (a,b,c), the for loop will go from 0 to size-1. We will decrement k when we reach leaf node (base case #2).

How do we find the empty string case?

If k is less than 0, return an empty string. This is base case 3. This is WRONG. Logical bug fix: After exploring all the possible paths, if k is still > 0, return an empty string. We should pass in k as a parameter to each recursive call.

Evaluate and Select Approach

Implementation

 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
def dfs(n, k, s, partial, result)
  if partial.size > n
    return
  end
  
  if partial.size == n
    result << partial.join
  end
  
  for i in (0...3)
    if partial.last != s[i]
      partial << s[i]
      dfs(n, k, s, partial, result)
      partial.pop
    end
  end
end

# @param {Integer[]} nums
# @return {Integer[]}    
def get_happy_string(n, k)
  s = ['a', 'b', 'c']
  output = []
  partial = []
  
  dfs(n, k, s, partial, output)
  
  if k-1 < output.size
    return output[k-1]
  else
    return ''
  end
end

Refactored Solution

 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
def dfs(n, s, partial, result)  
  if partial.size == n
    result << partial.join
    
    return
  end
  
  for i in (0...3)
    if partial.last != s[i]
      partial << s[i]
      dfs(n, s, partial, result)
      partial.pop
    end
  end
end

# @param {Integer[]} nums
# @return {Integer[]}    
def get_happy_string(n, k)
  s = ['a', 'b', 'c']
  output = []
  partial = []
  
  dfs(n, s, partial, output)
  
  if k-1 < output.size
    return output[k-1]
  else
    return ''
  end
end

 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
# @param {Integer} n
# @param {Integer} k
# @return {String}
def dfs(n, k, s, partial)
  if partial.size == n
    @counter -= 1
    if @counter == 0
      @result = partial.join
    end
    
    return
  end
  
  s.each do |c|
    unless partial[-1] == c
      partial << c
      dfs(n, k, s, partial)
      partial.pop
    end
  end 
end

def get_happy_string(n, k)
  @result = ''
  @counter = k
  
  dfs(n, @counter, ['a','b', 'c'], []) 
  @result
end

Counter and result must be available across all recursive calls. Otherwise this approach will not work.

PROBLEM DEFINITION

Define the Terms

Define the Interface Input: Output:

Identify Implicit Inputs

Define the Goal

Identify the Constraints

Determine the Scope List assumptions Define boundaries of the problem

Search the Problem Space Look for clues in the problem statement

Classify the Problem Decontextualize the Problem

Can you think of this problem in a different way?

Can you reframe it?

PROBLEM REPRESENTATION

Analyze the Input and Output

Analyze the Examples

Consider the Simple Cases First

Find missing cases

Find edge cases

Solve the Problem by Hand

Recognize the Pattern Describe the Pattern

Distill the Observations to Create Insights

Identify the Invariants

Consider Approaches

Shortcomings

Evaluate and Select

Brute Force Approach

Analyze Time and Space Complexity

Time: O( ) Space: O( )

Outline the Solution

Key Takeaways

Reflect

What went right?

What went wrong?

What can we improve next time?

 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
def dfs(n, s, partial, result)  
  if partial.size == n
    result << partial.join

    return
  end
  
  for i in (0...3)
    if partial.last != s[i]
      partial << s[i]
      dfs(n, s, partial, result)
      partial.pop
    end
  end
end

# @param {Integer[]} nums
# @return {Integer[]}    
def get_happy_string(n, k)
  s = ['a', 'b', 'c']
  output = []
  partial = []
  
  dfs(n, s, partial, output)
  
  if k-1 < output.size
    return output[k-1]
  else
    return ''
  end
end