Find the longest subsequence of words such that adjacent chosen words come from different groups and their lengths differ by exactly one character.
Problem
You are given an array of strings words and an array of integers groups, both of length n.
Choose a subsequence of indices i1 < i2 < ... < ik such that:
groups[ij] != groups[ij+1]for every adjacent pair in the subsequence.- The chosen words are pairwise comparable under a one-step difference rule: for any adjacent chosen words, the two words must have the same length and differ in exactly one character or differ by exactly one insertion/deletion in the way defined by the original problem setting.
Return the longest valid subsequence of indices, or its maximum length depending on the exact task formulation.
This is a dynamic programming problem where each state considers the best subsequence ending at a given word and transitions from earlier compatible words.
Input Format
words: array of stringsgroups: array of integers of the same length aswords
The exact platform version may ask for the length of the subsequence rather than the subsequence itself.
Output Format
Return the maximum length of a valid subsequence.
Constraints
1 <= n <= $10^{3}$is a safe interview-scale assumption for this formulation.- String lengths are small to moderate.
groups.length == words.length.- The answer should respect the alternating-group constraint on adjacent chosen elements.
Example 1
Input
words = ["a","b","ab","ac"], groups = [1,2,1,2]
Output
4
Explanation
One valid subsequence is ["a", "b", "ab", "ac"]. Adjacent groups alternate, and each step satisfies the allowed word-compatibility rule.
Example 2
Input
words = ["abcd","abce","abde"], groups = [1,1,2]
Output
2
Explanation
"abcd" and "abce" cannot both be used if the adjacent group condition is violated. A best valid subsequence has length 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.