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

class Solution {
public:
    string constructHappyString(int length, int position) {
        int totalPossible = 3 * (1 << (length - 1));
        if (position > totalPossible) return "";

        string happyString(length, 'a');
        unordered_map<char, char> smallerNeighbor = {
            {'a', 'b'}, {'b', 'a'}, {'c', 'a'}
        };
        unordered_map<char, char> largerNeighbor = {
            {'a', 'c'}, {'b', 'c'}, {'c', 'b'}
        };

        int startPositionA = 1;
        int startPositionB = startPositionA + (1 << (length - 1));
        int startPositionC = startPositionB + (1 << (length - 1));

        if (position < startPositionB) {
            happyString[0] = 'a';
            position -= startPositionA;
        } else if (position < startPositionC) {
            happyString[0] = 'b';
            position -= startPositionB;
        } else {
            happyString[0] = 'c';
            position -= startPositionC;
        }

        for (int i = 1; i < length; i++) {
            int midpoint = (1 << (length - i - 1));
            if (position < midpoint) {
                happyString[i] = smallerNeighbor[happyString[i - 1]];
            } else {
                happyString[i] = largerNeighbor[happyString[i - 1]];
                position -= midpoint;
            }
        }

        return happyString;
    }
};

This solution provides a method to construct the k-th lexicographical "happy string" of a given length. A "happy string" is a string where no two adjacent letters are the same, and it only consists of the characters 'a', 'b', and 'c'.

• The code initially calculates the total number of possible happy strings using the formula 3 * (1 << (length - 1)). It returns an empty string if the position is greater than totalPossible since it is out of the valid range.

• The unordered_map data structures smallerNeighbor and largerNeighbor facilitate the determination of the next character in the string based on the previous character, ensuring that no two consecutive characters are the same.

• Depending on the position, the first character of the string (happyString[0]) is determined, then, position is adjusted relative to the start position of each character block ('a', 'b', 'c').

• The for loop constructs the string character by character:

  • It calculates the midpoint for deciding whether the next character should be the smaller or larger neighbor.
  • Depending on whether the position is less than the midpoint, it assigns the next character in happyString.

• Finally, it returns the constructed happyString.

This solution effectively utilizes bit manipulation and direct addressing via hash maps to quickly determine each character of the happy string without generating all potential candidates explicitly. This is particularly efficient for generating such strings of considerable length.

public class Solution {

    public String generateHappyString(int length, int position) {
        int totalStrings = 3 * (1 << (length - 1));

        if (position > totalStrings) return "";

        StringBuilder happyString = new StringBuilder(length);
        for (int i = 0; i < length; i++) {
            happyString.append('a');
        }

        Map<Character, Character> smallerNext = new HashMap<>();
        smallerNext.put('a', 'b');
        smallerNext.put('b', 'a');
        smallerNext.put('c', 'a');

        Map<Character, Character> largerNext = new HashMap<>();
        largerNext.put('a', 'c');
        largerNext.put('b', 'c');
        largerNext.put('c', 'b');

        int indexA = 1;
        int indexB = indexA + (1 << (length - 1));
        int indexC = indexB + (1 << (length - 1));

        if (position < indexB) {
            happyString.setCharAt(0, 'a');
            position -= indexA;
        } else if (position < indexC) {
            happyString.setCharAt(0, 'b');
            position -= indexB;
        } else {
            happyString.setCharAt(0, 'c');
            position -= indexC;
        }

        for (int idx = 1; idx < length; idx++) {
            int midPoint = (1 << (length - idx - 1));

            if (position < midPoint) {
                happyString.setCharAt(
                    idx,
                    smallerNext.get(happyString.charAt(idx - 1))
                );
            } else {
                happyString.setCharAt(
                    idx,
                    largerNext.get(happyString.charAt(idx - 1))
                );
                position -= midPoint;
            }
        }

        return happyString.toString();
    }
}

This Java program defines a function generateHappyString that generates the k-th lexicographical "happy string" of a specified length. A happy string is one where no adjacent characters are the same. Here’s a breakdown of how this program functions:

• Initial Calculations and Setup:

  • First, calculate the total number of possible happy strings of the given length using the formula 3 * (1 << (length - 1)).
  • If the requested position exceeds the total number of happy strings, return an empty string.
  • Initialize a StringBuilder to build the happy string character by character, pre-filled with 'a'.

• Mapping For Next Characters:

  • Two mappings (smallerNext and largerNext) determine the next characters that can follow the current character based on avoiding adjacent repetitions.

• Determining the Starting Character:

  • Calculate indices for each possible starting character ('a', 'b', 'c') of the happy string.
  • Use these indices to determine the first character of the happy string based on the given position and adjust the position for subsequent calculations.

• Building the String:

  • For each subsequent character in the string (from the second to the last), determine whether the position falls within the first half or the second half of the range for the current length. This decision affects whether the next character is chosen from the smallerNext or largerNext map.
  • Adjust position as needed for the next iteration.

• Output:

  • Convert the StringBuilder to a string and return it, providing the k-th lexicographical happy string of the specified length.

This structured approach efficiently calculates the required happy string by constructing it character by character, optimizing both time and space complexity.

class Solution:
    def generateHappyString(self, length: int, position: int) -> str:
        num_happy_strings = 3 * (1 << (length - 1))  # Calculate total happy strings

        if position > num_happy_strings:
            return ""

        happy_string = ['a'] * length  # Initialize happy_string

        # Next available characters based on current character
        next_lower = {"a": "b", "b": "a", "c": "a"}
        next_upper = {"a": "c", "b": "c", "c": "b"}

        # Indices for strings starting with each character
        index_a = 1
        index_b = index_a + (1 << (length - 1))
        index_c = index_b + (1 << (length - 1))

        # Set first character
        if position < index_b:
            happy_string[0] = "a"
            position -= index_a
        elif position < index_c:
            happy_string[0] = "b"
            position -= index_b
        else:
            happy_string[0] = "c"
            position -= index_c

        # Build the string based on position
        for i in range(1, length):
            mid_point = 1 << (length - i - 1)
            if position < mid_point:
                happy_string[i] = next_lower[happy_string[i - 1]]
            else:
                happy_string[i] = next_upper[happy_string[i - 1]]
                position -= mid_point

        return "".join(happy_string)

The provided solution in Python generates the k-th lexicographical "happy string" of a given length n. A "happy string" is a string that meets the condition where no two adjacent characters are the same, and it uses exclusively the characters 'a', 'b', and 'c'.

Here is a breakdown of the approach taken:

• Initial Calculations:

  • The total number of possible happy strings of length n is calculated using the formula 3 * (1 << (n - 1)).
  • If the requested position k (zero-indexed) exceeds the number of happy strings, an empty string is returned as no valid string exists at that position.

• Initialization:

  • An initial happy string is created with a default repeating character 'a', which will be modified as the algorithm progresses.
  • Auxiliary dictionaries, next_lower and next_upper, are defined to facilitate the selection of valid characters that can follow each character without forming an unhappy string.

• Position Determination:

  • Based on the position index, the initial character of the happy string is determined. This is segmented based on total counts of strings starting with 'a', 'b', or 'c'.
  • The position index is adjusted by subtracting the starting index of the respective initial character.

• String Construction:

  • The string is progressively built character by character from the second position to the end. The construction uses binary decisions based on the midpoint of each subset of possibilities, utilizing the next_lower and next_upper dictionaries.
  • This binary choice elegantly divides the possibilities into two groups at each step, refining the placement in the desired k-th position.

• Final Output:

  • The result is the concatenation of the characters in the list that formed during the progressive construction based on the provided position. This final string is a valid happy string at the requested position k.

This solution is efficient because it uses bitwise operations to halve the remaining options at each step, thus constructing the string in linear time concerning the length of the string n.