Tap here to switch tabs
Problem
Submissions

Problem: Lexicographically Smallest Generated String

Lexicographically Smallest Generated String gives a pattern and target string. Find the smallest string whose true windows equal the target and false windows do not, or return empty if impossible.

Statement

You are given two strings, str1 of length n and str2 of length m.

A string word of length n+m−1n + m - 1 is generated such that for each index i from 00 to n−1n - 1:

  • If str1[i] == 'T', the substring of length m starting at index i, word[i .. i + m - 1], is equal to str2.

  • If str1[i] == 'F', the substring of length m starting at index i, word[i .. i + m - 1], is not equal to str2.

Return the lexicographically smallest string word that can be generated. If no such string satisfies the conditions, return an empty string "".

Constraints:

  • 1≤n=1 \leq n = str1.length ≤104\leq 10^4

  • 1≤m=1 \leq m = str2.length ≤500\leq 500

  • str1 consists only of 'T' and 'F'.

  • str2 consists only of lowercase English letters.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Lexicographically Smallest Generated String

Lexicographically Smallest Generated String gives a pattern and target string. Find the smallest string whose true windows equal the target and false windows do not, or return empty if impossible.

Statement

You are given two strings, str1 of length n and str2 of length m.

A string word of length n+m−1n + m - 1 is generated such that for each index i from 00 to n−1n - 1:

  • If str1[i] == 'T', the substring of length m starting at index i, word[i .. i + m - 1], is equal to str2.

  • If str1[i] == 'F', the substring of length m starting at index i, word[i .. i + m - 1], is not equal to str2.

Return the lexicographically smallest string word that can be generated. If no such string satisfies the conditions, return an empty string "".

Constraints:

  • 1≤n=1 \leq n = str1.length ≤104\leq 10^4

  • 1≤m=1 \leq m = str2.length ≤500\leq 500

  • str1 consists only of 'T' and 'F'.

  • str2 consists only of lowercase English letters.