A cryptographer is inspecting a tape of lowercase signal letters for occurrences of a two-letter passcode (the two letters of the passcode need not be distinct). A "match" is any subsequence of the tape -- reading left to right, skipping any letters as needed -- that spells the passcode exactly; every valid choice of positions counts as a separate match. Before counting matches, the cryptographer may splice exactly one extra copy of a single letter into the tape at any one position, including at the very front or the very back, and that spliced letter must be either the passcode's first letter or its second letter. Choose which letter to splice and where to splice it so as to maximize the number of passcode matches in the resulting tape, and report that maximum.
Line 1: the tape, a string of lowercase English letters. Line 2: the passcode, a string of exactly two lowercase English letters.
A single integer: the maximum number of passcode matches achievable after at most one splice.
Example 1
Input
abdcbc ac
Expected
4
Explanation
The tape already has 2 passcode matches: its single 'a' paired with each of its two 'c's. It contains 1 occurrence of 'a' and 2 occurrences of 'c'. Splicing in one extra 'a' at the front adds one more match against each existing 'c' (+2), for a total of 4; splicing a 'c' at the back would only add +1 (pairing with the single existing 'a'). The best choice gives 4.
Example 2
Input
aabb ab
Expected
6
Explanation
The tape has 4 matches already (2 a's times 2 b's). Splicing an extra 'a' at the front adds +2 (it pairs with both existing b's), and splicing an extra 'b' at the back also adds +2 (it pairs with both existing a's) -- either choice is equally best, giving a total of 6.
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 →