Thomas Ngo

Software Engineer

3 minute read

Problem Statement

problem

Intuition

The problem requires generating a lexicographically sorted list of “happy strings” of length n using the characters ‘a’, ‘b’, and ‘c’. A “happy string” is defined as a string where no two consecutive characters are the same. Given an integer k, we return the k-th lexicographically smallest happy string.

The first intuition is to use backtracking to generate all possible happy strings and store them in a min-heap to track the k-th smallest string efficiently.

Approach

  1. Use a recursive function generate_happy_string to generate all possible happy strings of length n.
  2. Maintain a min-heap (min_heap) to store the happy strings in lexicographic order.
  3. At each step, append one of the characters (‘a’, ‘b’, or ‘c’) to the current string, ensuring that the last character is not repeated.
  4. Once the length of the string reaches n, add it to the heap.
  5. Return the k-th smallest string from the heap, or an empty string if k is out of bounds.

Complexity

  • Time Complexity:

    • Since each position in the string can be filled with at most 2 choices (excluding the previous character), the total number of happy strings is at most O(2^n). Since heap operations take O(log k), the overall complexity is approximately O(2^n log k).

  • Space Complexity:

    • The recursion depth is O(n), and the heap can store up to O(2^n) elements in the worst case. Thus, the space complexity is O(2^n).

Code

import heapq

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        min_heap = []

        def generate_happy_string(letters, curr, start):
            if len(curr) == n:
                heapq.heappush(min_heap, "".join(curr))
                return

            for i in range(3):
                if curr and curr[-1] == letters[i]:
                    continue
                generate_happy_string(letters, curr + [letters[i]], i)

        generate_happy_string("abc", [], 0)

        return min_heap[k - 1] if 0 <= k - 1 < len(min_heap) else ""

Editorial

Approach 1: Backtracking

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        current_string = ""
        happy_strings = []
        # Generate all happy strings of length n
        self.generate_happy_strings(n, current_string, happy_strings)

        # Check if there are at least k happy strings
        if len(happy_strings) < k:
            return ""

        # Sort the happy strings in lexicographical order
        happy_strings.sort()

        return happy_strings[k - 1]

    def generate_happy_strings(
        self, n: int, current_string: str, happy_strings: list
    ):
        # If the current string has reached the desired length, add it to the list
        if len(current_string) == n:
            happy_strings.append(current_string)
            return

        # Try adding each character ('a', 'b', 'c') to the current string
        for current_char in ["a", "b", "c"]:
            # Skip if the current character is the same as the last character
            if len(current_string) > 0 and current_string[-1] == current_char:
                continue

            # Recursively generate the next character
            self.generate_happy_strings(
                n, current_string + current_char, happy_strings
            )
  • time: O(n * 2^n)
  • space: O(2^n)

Approach 2: Optimized Recursion

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        self.current_string = ""
        self.result = ""
        self.index_in_sorted_list = 0

        # Generate happy strings and track the k-th string
        self.generate_happy_strings(n, k)
        return self.result

    def generate_happy_strings(self, n, k):
        # If the current string has reached the desired length
        if len(self.current_string) == n:
            # Increment the count of generated strings
            self.index_in_sorted_list += 1

            # If this is the k-th string, store it in the result
            if self.index_in_sorted_list == k:
                self.result = self.current_string
            return

        # Try adding each character ('a', 'b', 'c') to the current string
        for current_char in ["a", "b", "c"]:
            # Skip if the current character is the same as the last one
            if (
                len(self.current_string) > 0
                and self.current_string[-1] == current_char
            ):
                continue

            self.current_string += current_char

            # Recursively generate the next character
            self.generate_happy_strings(n, k)

            # If the result is found, stop further processing
            if self.result != "":
                return

            # Backtrack by removing the last character
            self.current_string = self.current_string[:-1]

Approach 3: Iterative Using a Stack

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        strings_stack = []
        index_in_sorted_list = 0
        strings_stack.append("")  # Start with an empty string

        while strings_stack:
            current_string = strings_stack.pop()

            # If we have built a string of length n, count it
            if len(current_string) == n:
                index_in_sorted_list += 1
                # If we reach the k-th happy string, return it
                if index_in_sorted_list == k:
                    return current_string
                continue

            # Expand the current string by adding 'a', 'b', or 'c'
            # Ensuring lexicographic order by pushing in reverse
            for current_char in reversed(["a", "b", "c"]):
                # Avoid consecutive identical characters
                if (
                    len(current_string) == 0
                    or current_string[-1] != current_char
                ):
                    strings_stack.append(current_string + current_char)
        return ""

You may also enjoy