Generate Valid Tweet Topic Sequences
Twitter's content organization often involves grouping related tweets into coherent "threads" or "moments." Imagine a system designed to help users or automated tools understand and generate structured content. This problem focuses on generating all possible valid sequences of topics for a multi-tweet thread, given a set of predefined rules for how topics can transition from one tweet to the next. This helps ensure thematic consistency and discoverability within longer discussions.
Implement a function generateValidTopicSequences that, given a set of allowed topic transitions, a starting topic for the thread, and a desired total length for the topic sequence, returns all possible valid topic sequences.
A topic sequence is considered valid if:
startTopic.maxLength.(T_i, T_{i+1}) in the sequence is an allowed transition as specified in the transitions input.generateValidTopicSequences(transitions: string[][], startTopic: string, maxLength: number): string[][]transitions: An array of string[] pairs, where each inner [topicA, topicB] array indicates that a tweet with topicA can be directly followed by a tweet with topicB.startTopic: A string representing the initial topic of the thread. All generated sequences must begin with this topic.maxLength: A number indicating the exact desired length of each valid topic sequence.Returns:
An array of string[], where each inner string[] represents a unique valid topic sequence. The order of sequences in the output array does not matter.
[].transitions (e.g., ["Sports", "Sports"]).Examples
Example 1
Input:
transitions = [["Sports", "News"], ["News", "Tech"], ["News", "Politics"], ["Tech", "Sports"]], startTopic = "Sports", maxLength = 3
Output:
[["Sports","News","Tech"],["Sports","News","Politics"]]
Note:
From 'Sports', only 'News' is possible. From 'News', both 'Tech' and 'Politics' are possible, leading to two valid sequences of length 3.
Example 2
Input:
transitions = [["A", "B"], ["B", "C"], ["C", "A"]], startTopic = "A", maxLength = 2
Output:
[["A","B"]]
Note:
From 'A', only 'B' is possible. The sequence 'A', 'B' has length 2, which matches maxLength.
Example 3
Input:
transitions = [["X", "Y"], ["Y", "Z"]], startTopic = "X", maxLength = 3
Output:
[]
Note:
From 'X', only 'Y' is possible. From 'Y', only 'Z' is possible. The sequence 'X', 'Y', 'Z' has length 3. This is the only path, but the output order doesn't matter for the array of sequences.
Constraints
transitions will contain between 1 and 50 pairs.startTopic will always be one of the topics present in the transitions list.maxLength will be between 1 and 10.startTopic (it's guaranteed to be valid).maxLength values where the number of sequences would be astronomically high (the current maxLength constraint keeps this manageable for the given time budget).transitions.Loading editor...