Problem Statement in English

You’re given a string s of length n consisting of characters ‘T’ and ‘F’, and another string t of length m. You need to generate a string of length n + m - 1 that satisfies the following conditions:

  1. For every index i (0-indexed) where s[i] is ‘T’, the substring of the generated string starting at index i and having length m must be equal to t.
  2. For every index i where s[i] is ‘F’, the substring of the generated string starting at index i and having length m must not be equal to t.

You need to return the lexicographically smallest string that satisfies these conditions. If there is no such string, return an empty string.

Approach

We use an optimistic greedy approach.

We first process all the ‘T’ characters in s and fill the corresponding positions in the answer string according to t. If while processing a ‘T’ character we find a conflict (i.e., a position that has already been filled with a different character), we can immediately return an empty string since it’s impossible to satisfy the conditions.

Next we fill all the remaining ‘?’ characters with ‘a’ to get the lexicographically smallest string.

Finally, we process all the ‘F’ characters in s. For each ‘F’, we check if the corresponding substring in the answer string matches t. If it does, we need to change at least one character in that substring to ensure it does not match t.

We look for the last ‘?’ character in that substring (which we initially set to ‘a’) and change it to ‘b’. If there are no ‘?’ characters left to change, it means we cannot satisfy the conditions for that ‘F’, and we return an empty string.

And we’re done!

Solution in Python


class Solution:
    def generateString(self, s: str, t: str) -> str:
        n, m = len(s), len(t)
        ans = ['?'] * (n + m - 1)  # ? indicates a pending position
        
        # Process 'T'
        for i, b in enumerate(s):
            if b != 'T':
                continue
            # The substring must match t
            for j, c in enumerate(t):
                v = ans[i + j]
                if v != '?' and v != c:
                    return ""
                ans[i + j] = c
        
        old_ans = ans
        ans = ['a' if c == '?' else c for c in ans]  # Initial default is 'a'
        
        # Process 'F'
        for i, b in enumerate(s):
            if b != 'F':
                continue
            # Substring must not equal t
            if ''.join(ans[i: i + m]) != t:
                continue
            # Locate the last pending position to modify
            for j in range(i + m - 1, i - 1, -1):
                if old_ans[j] == '?':  # Change 'a' to 'b'
                    ans[j] = 'b'
                    break
            else:
                return ""
        return ''.join(ans)

Complexity

  • Time: $O(n \cdot m)$
    Since we may need to check each ‘F’ character against the substring of length m and also fill the answer string.

  • Space: $O(n + m)$
    Since we store the answer string and also need to keep track of the original pending positions.

Mistakes I Made

I had to look this up :(

And we are done.