Theme Sequence Arrangement
At Livspace, designing cohesive yet dynamic spaces is paramount. Imagine we are curating a virtual design walkthrough for a client, presenting a sequence of distinct design elements. To ensure a harmonious flow and prevent monotony, we need to arrange themes for these elements carefully. This problem simulates finding all valid thematic sequences for a series of design elements, adhering to specific constraints on theme usage and adjacency.
Implement a function findThemeSequences that generates all possible valid sequences of themes for k design elements. A sequence is considered valid if it satisfies the following conditions:
Function Signature:
function findThemeSequences(k: number, themes: string[], maxUsages: { [key: string]: number }): string[][]
Parameters:
k: A number representing the total count of design elements in the sequence. The length of each valid theme sequence must be k.themes: An array of unique strings, where each string is the name of an available design theme (e.g., "Modern", "Classic", "Bohemian").maxUsages: An object (or hash map) where keys are theme names (from the themes array) and values are numbers indicating the maximum allowed occurrences of that theme across the entire k-length sequence.Return Value:
string[][] (array of string arrays). Each inner array represents a unique, valid sequence of themes. The order of sequences in the outer array does not matter.k will always be a positive integer (k >= 1).themes will always contain at least one theme (themes.length >= 1).maxUsages will always contain entries for all themes present in the themes array.Examples
Example 1
Input:
k = 3, themes = ["Modern", "Classic"], maxUsages = {"Modern": 2, "Classic": 1}
Output:
[["Modern","Classic","Modern"]]
Note:
The sequence ["Modern","Classic","Modern"] is valid: 'Modern' is used 2 times (max 2), 'Classic' is used 1 time (max 1), and no adjacent themes are the same. Sequences like ["Classic","Modern","Classic"] are invalid because 'Classic' would be used 2 times (max 1). Sequences like ["Modern","Modern","Classic"] are invalid due to adjacent identical themes.
Example 2
Input:
k = 2, themes = ["A", "B", "C"], maxUsages = {"A": 1, "B": 1, "C": 1}
Output:
[["A","B"],["A","C"],["B","A"],["B","C"],["C","A"],["C","B"]]
Note:
All 2-element permutations of 'A', 'B', 'C' are valid, as each theme is used at most once and no adjacent themes are the same.
Example 3
Input:
k = 4, themes = ["Red", "Blue"], maxUsages = {"Red": 2, "Blue": 2}
Output:
[["Red","Blue","Red","Blue"],["Blue","Red","Blue","Red"]]
Note:
Only two alternating sequences are valid. For example, ["Red","Blue","Red","Blue"] uses 'Red' twice and 'Blue' twice, and has no adjacent identical themes. Any sequence with adjacent identical themes (e.g., ["Red","Red","Blue","Blue"]) or exceeding max usage (not applicable here as sum of maxUsages equals k) would be invalid.
Constraints
1 <= k <= 71 <= themes.length <= 5themes is a non-empty string with length between 1 and 20 characters.1 <= maxUsages[theme] <= k for all themes.maxUsages values might be less than, equal to, or greater than k.Loading editor...