We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 1516

Difficulty: Medium

Paid? No

Companies: Bloomberg, Meta, Google, Microsoft

Problem Description

Given integers n and k, find the kth lexicographical happy string of length n. A happy string is composed only of the characters ['a', 'b', 'c'] and has no two adjacent characters that are the same. If there are fewer than k happy strings of length n, return an empty string.

Key Insights

  • Use backtracking to generate all happy strings since n is small (1 <= n <= 10).
  • Ensure lexicographical order by always processing characters in the order: 'a', 'b', 'c'.
  • Check the last character to avoid adding a duplicate for consecutive positions.
  • Stop the recursion once the kth string is obtained to save unnecessary computations.

Space and Time Complexity

Time Complexity: O(3^n) in the worst case, though early termination reduces the average case. Space Complexity: O(n) due to recursion depth and the space used to store each string.

Solution

We use a recursive backtracking algorithm to build strings character by character. At each recursion level, try adding 'a', 'b', or 'c' (in order) if it does not match the last character of the current string to maintain the happy string property. A counter tracks the number of valid strings generated; once the kth valid string is reached, store it and cancel further recursive calls. This method leverages the limited input range to remain efficient even though the worst-case complexity is exponential.

Code Solutions

# Python solution with line-by-line comments
def getHappyString(n, k):
    # List to hold the kth happy string once found
    result = []
    # Counter to track how many happy strings have been formed
    count = [0]
    
    # Helper function using backtracking
    def backtrack(current):
        # Check if the current string length equals n
        if len(current) == n:
            count[0] += 1  # Increment counter for each valid string
            if count[0] == k:
                result.append(current)  # Found kth string, store result
            return
        
        # Try each character in lex order
        for c in ['a', 'b', 'c']:
            # Ensure the new character is not equal to the last character
            if not current or current[-1] != c:
                backtrack(current + c)
                # Early exit if kth string is already found
                if result:
                    return

    backtrack("")
    return result[0] if result else ""

# Sample test
print(getHappyString(3, 9))  # Expected Output: "cab"
← Back to All Questions