Shared Catalog Spine Codes
Count distinct longest common subsequences of two strings by first letter
A library has two historical records of spine codes, record_a and record_b. Each record is a string of lowercase English letters.
A shared code is a nonempty string that can be obtained from each record by deleting zero or more characters without changing the order of the remaining characters. The librarians want only shared codes of the greatest possible length.
Return a list of 26 integers. Entry 0 counts the distinct greatest-length shared codes beginning with a, entry 1 counts those beginning with b, and so on through z. Return each count modulo 1,000,000,007.
Two shared codes are distinct only when their resulting strings differ. Different choices of positions that produce the same string do not count separately.
If there is no nonempty shared code, return 26 zeros.
Examples
Example 1
Input: record_a = "abc", record_b = "bac" Output: [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
The greatest-length shared codes are `ac` and `bc`. They contribute to the entries for `a` and `b`, respectively.
Example 2
Input: record_a = "aaaa", record_b = "aa" Output: [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
The greatest-length shared code is `aa`. Although either record offers multiple position choices, this resulting string is counted only once.
Example 3
Input: record_a = "abc", record_b = "xyz" Output: [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
The records have no letter in common, so there is no nonempty shared code.
Constraints
- 0 <= record_a.length, record_b.length <= 700
- Both records contain only lowercase English letters.
- Counts must be returned modulo 1,000,000,007.
The intended solution uses O(26 * n * m + 26 * (n + m)) time and O(n * m + 26 * (n + m)) space. An empty continuation counts as one completion inside the dynamic program, but the empty string is not included in the returned histogram.
Hints
Show hint 1Hint 1
Compute the greatest common subsequence length for every pair of suffixes.
Show hint 2Hint 2
For a proposed next letter, use its earliest occurrence in each suffix. This canonical choice represents every possible resulting string beginning with that letter without counting multiple embeddings.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the lexicographically smallest greatest-length shared code?
- How could you count distinct shared codes of every length rather than only the greatest length?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem