Longest Common Contiguous Browser History
Roblox● MediumFULLTIMEPHONE SCREENProblem statement
Two arrays historyA and historyB list the URL tokens visited by two users in chronological order. A URL appears at most once in each user’s history.
Return the longest contiguous sequence of URL tokens that appears in both histories in the same order. Contiguous means consecutive entries in each history; skipping entries is not allowed. Compare complete tokens exactly and case-sensitively.
For this exercise, assume ties choose the sequence with the earliest starting index in historyA, then the earliest starting index in historyB. Return an empty array if either history is empty or no token is shared.
Function
longestCommonHistory(historyA: String[], historyB: String[]) → String[]Examples
Example 1
historyA = ["/start","/pink","/register","/orange","/red","a"]historyB = ["/start","/green","/blue","/pink","/register","/orange","/one/two"]return = ["/pink","/register","/orange"]The exact reported comparison of user 0 and user 1 returns this longest shared contiguous sequence.
Example 2
historyA = ["/start","/green","/blue","/pink","/register","/orange","/one/two"]historyB = ["a","/one","/two"]return = []The exact reported comparison of user 1 and user 2 returns this longest shared contiguous sequence.
Example 3
historyA = ["a","/one","/two"]historyB = ["/start","/pink","/register","/orange","/red","a"]return = ["a"]The exact reported comparison of user 2 and user 0 returns this longest shared contiguous sequence.
Example 4
historyA = ["a"]historyB = ["a","/one","/two"]return = ["a"]The exact reported comparison of user 5 and user 2 returns this longest shared contiguous sequence.
Example 5
historyA = ["/pink","/orange","/yellow","/plum","/blue","/tan","/red","/amber","/HotRodPink","/CornflowerBlue","/LightGoldenRodYellow","/BritishRacingGreen"]historyB = ["/pink","/orange","/amber","/BritishRacingGreen","/plum","/blue","/tan","/red","/lavender","/HotRodPink","/CornflowerBlue","/LightGoldenRodYellow"]return = ["/plum","/blue","/tan","/red"]The exact reported comparison of user 3 and user 4 returns this longest shared contiguous sequence.
Example 6
historyA = ["/pink","/orange","/amber","/BritishRacingGreen","/plum","/blue","/tan","/red","/lavender","/HotRodPink","/CornflowerBlue","/LightGoldenRodYellow"]historyB = ["/pink","/orange","/yellow","/plum","/blue","/tan","/red","/amber","/HotRodPink","/CornflowerBlue","/LightGoldenRodYellow","/BritishRacingGreen"]return = ["/plum","/blue","/tan","/red"]The exact reported comparison of user 4 and user 3 returns this longest shared contiguous sequence.
Constraints
- For this exercise, assume
0 <= historyA.length, historyB.length <= 500. - For this exercise, assume each token contains 1 through 50 printable ASCII characters and is compared as an opaque string.
- No token is repeated within either individual history; the same token may appear once in each history.