A sign shop produces long parade banners by pressing a single rubber stamp onto a blank strip over and over, edge-to-edge with no gaps and no overlaps, until the strip is completely covered — so every banner the shop makes is really just one stamp pattern repeated some whole number of times. A customer dropped off two finished banners and wants to know the longest stamp pattern that could have produced BOTH banners, where the pattern may be repeated a different (positive) number of times for each banner. If no single non-empty pattern could have produced both banners, the shop should say so.
banner1, a non-empty string of uppercase English letters.banner2, a non-empty string of uppercase English letters.Print the longest string pattern such that banner1 and banner2 are each equal to pattern repeated some positive whole number of times. If no such non-empty pattern exists, print an empty line.
1 <= |banner1|, |banner2| <= 1000A-ZExample 1
Input
ABABAB ABAB
Expected
AB
Explanation
Banner 1's length is 6 and banner 2's length is 4, so any valid pattern's length must divide both, meaning it can be at most gcd(6, 4) = 2. The length-2 prefix of banner 1, 'AB', repeated 3 times gives 'ABABAB' (banner 1) and repeated 2 times gives 'ABAB' (banner 2), so 'AB' is a valid shared pattern — and since 2 is the largest length that could possibly work, 'AB' is the answer.
Example 2
Input
LEET CODE
Expected
(empty)Explanation
Both banners have length 4, so any valid pattern's length must divide gcd(4, 4) = 4, i.e. it could only be length 4, 2, or 1. Length 4 would mean banner 1 itself is the pattern, but 'LEET' repeated once is 'LEET', not 'CODE', so that fails. The length-2 prefix 'LE' and the length-1 prefix 'L' fail too, since their letters don't even appear in matching positions of 'CODE'. No non-empty pattern produces both banners, so the shop prints an empty line.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →