Frontend School

Theme Sequence Arrangement

DSA
medium

Theme Sequence Arrangement

Medium
Backtracking
Recursion
Combinatorics

Overview

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.

What you need to do / Task

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:

  1. No two adjacent elements in the sequence can be assigned the same theme.
  2. Each theme can be used a maximum number of times throughout the entire sequence, as specified.

Input & output

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:

  • A 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.

Clarifications

  • 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.
  • Theme names are case-sensitive.

Examples

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= k <= 7
  • 1 <= themes.length <= 5
  • Each theme name in themes is a non-empty string with length between 1 and 20 characters.
  • 1 <= maxUsages[theme] <= k for all themes.
  • The sum of all maxUsages values might be less than, equal to, or greater than k.

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies and generates all valid theme sequences according to the specified constraints.
  • Backtracking Logic: Effective implementation of a recursive backtracking approach to explore the solution space.
  • State Management: Proper handling of the current sequence and theme usage counts throughout the recursion.
  • Code Quality: Clarity, readability, and maintainability of the code, including appropriate variable naming and structure.

Loading editor...