Smallest String by a Match Plan

Hard

You are given a plan plan of length n made of the characters T and F, and a stamp string stamp of length m. Build a string result of length n + m - 1 from lowercase English letters so that for every position i from 0 to n - 1: - if plan[i] == 'T', the piece result[i..i + m - 1] is exactly stamp; - if plan[i] == 'F', that piece differs from stamp. Return the lexicographically smallest such string. If no such string exists, return an empty string.

Example 1

plan="FTF", stamp="ca" → 'acaa'

The result has length 3 + 2 − 1 = 4. The T at position 1 makes characters 1–2 equal ca. The free positions 0 and 3 get a: the windows ac and aa differ from ca, as both F require. The answer is acaa.

Example 2

plan="TT", stamp="ab" → ''

The first window needs b at position 1, the second needs a there. They clash, so the answer is an empty string.

Example 3

plan="FF", stamp="a" → 'bb'

No letter may be a, so the smallest string is bb.

Constraints

1 ≤ len(plan) ≤ 10⁴
1 ≤ len(stamp) ≤ 500
plan consists only of the characters T and F
stamp consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String String Matching

Similar problems

Does the Text Fit the Pattern Hard Palindrome by Adding Letters in Front Hard Equal Letters Kept Apart Hard Harden the Password Hard Distinct Word Shorthands Hard

Input

plan="FTF", stamp="ca"

Expected

'acaa'

Run checks the first 3 tests in your browser. Submit checks all 269 tests on the server, hidden ones included.