# Lexicographically Smallest Generated String
**Difficulty:** HARD
[External](https://leetcode.com/problems/lexicographically-smallest-generated-string)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-generated-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** String
**Companies:** [Barclays](https://scaleengineer.com/companies/barclays)
---
## Problem
You are given two strings, `str1` and `str2`, of lengths `n` and `m`, respectively.

A string `word` of length `n + m - 1` is defined to be **generated** by `str1` and `str2` if it satisfies the following conditions for **each** index `0 <= i <= n - 1`:

* If `str1[i] == 'T'`, the **substring** of `word` with size `m` starting at index `i` is **equal** to `str2`, i.e., `word[i..(i + m - 1)] == str2`.
* If `str1[i] == 'F'`, the **substring** of `word` with size `m` starting at index `i` is **not equal** to `str2`, i.e., `word[i..(i + m - 1)] != str2`.

Return the **lexicographically smallest** possible string that can be **generated** by `str1` and `str2`. If no string can be generated, return an empty string `""`.

**Example 1:**

**Input:** str1 = "TFTF", str2 = "ab"

**Output:** "ababa"

**Explanation:**

#### The table below represents the string `"ababa"`

| Index | T/F | Substring of length m |
| ----- | --- | --------------------- |
| 0     | 'T' | "ab"                  |
| 1     | 'F' | "ba"                  |
| 2     | 'T' | "ab"                  |
| 3     | 'F' | "ba"                  |

The strings `"ababa"` and `"ababb"` can be generated by `str1` and `str2`.

Return `"ababa"` since it is the lexicographically smaller string.

**Example 2:**

**Input:** str1 = "TFTF", str2 = "abc"

**Output:** ""

**Explanation:**

No string that satisfies the conditions can be generated.

**Example 3:**

**Input:** str1 = "F", str2 = "d"

**Output:** "a"

**Constraints:**

* `1 <= n == str1.length <= 104`
* `1 <= m == str2.length <= 500`
* `str1` consists only of `'T'` or `'F'`.
* `str2` consists only of lowercase English characters.

# Approaches
## Brute-force with Backtracking
A naive approach to this problem is to try generating all possible strings of length `n + m - 1` and checking if they satisfy the given conditions. The search space is `26^(n+m-1)`, which is enormous. We can use backtracking to explore this search space more intelligently.
**Time:** O(26^(n+m-1) * n * m) in the worst case without pruning. Pruning helps but the complexity remains exponential. This is infeasible. · **Space:** O(n+m) for the recursion stack depth and to store the candidate string.
**Pros:** Conceptually simple to understand.
**Cons:** Extremely inefficient, with a worst-case time complexity that is exponential in the length of the generated string.; Will not pass the time limits for the given constraints.
### Explanation
We can define a recursive function, say `generate(index, current_word)`, that tries to fill the `word` character by character from left to right (from `index = 0` to `n+m-2`).

At each `index`, we iterate through all possible characters from 'a' to 'z'. For each character, we place it at `current_word[index]` and recurse for the next index `index + 1`.

The base case for the recursion is when `index == n + m - 1`. At this point, we have a complete candidate `word`. We then verify if this `word` satisfies all `n` conditions given by `str1` and `str2`. If it does, we have found a valid generated string. Since we are exploring characters in lexicographical order ('a' through 'z'), the first valid string we find will be the lexicographically smallest one.

To optimize, we can add pruning to the backtracking. After placing a character at `current_word[index]`, we can check any conditions that have just become fully determined. For example, if `index` is `i + m - 1`, the substring `word[i : i+m]` is now complete. We can check the condition for `str1[i]` immediately. If it's violated, we can prune this entire branch of the search tree, avoiding unnecessary recursive calls.

Despite pruning, the worst-case time complexity remains exponential and is too slow for the given constraints.
### Algorithm
- Define a recursive function `solve(k, word)` which attempts to fill characters from index `k`.
- The base case is `k == n + m - 1`. A full `word` has been constructed.
- In the base case, validate the generated `word` against all `n` conditions from `str1`.
- If all conditions are met, this is a valid string. Since we explore lexicographically, this is the smallest one. Return it.
- If not, return a failure indicator.
- In the recursive step, for the current index `k`, loop through characters `c` from 'a' to 'z'.
- Set `word[k] = c`.
- Optionally, perform pruning by checking any newly completed constraints.
- Call `solve(k + 1, word)`.
- If the recursive call returns a valid string, propagate it up. Otherwise, continue the loop to try the next character.
- If the loop finishes without finding a solution, return a failure indicator.

## Greedy with Fixup
A much more efficient approach is a greedy one. We aim to construct the lexicographically smallest string. This means we should try to use the character 'a' as much as possible, and for other characters, use the smallest possible ones. The strategy involves three phases: first, satisfy all 'T' constraints; second, greedily fill the rest of the string with 'a'; third, verify and fix any violations of 'F' constraints.
**Time:** O(n * m). Phase 1 takes O(n * m) to fill 'T' constraints. Phase 2 is O(n+m). Phase 3 involves a loop of size `n`, and inside it, a substring comparison of length `m` and a potential fixup loop of length `m`, leading to O(n * m). The total complexity is dominated by O(n * m). · **Space:** O(n + m) to store the `word` character array and the `is_fixed` boolean array.
**Pros:** Efficient, with a polynomial time complexity.; Correctly finds the lexicographically smallest string by making greedy choices and minimal modifications.; Relatively straightforward to implement.
**Cons:** The logic requires careful handling of array indices and constraints.; Involves multiple passes over the data structures.
### Explanation
The algorithm works as follows:

1.  **Phase 1: Handle 'T' Constraints**
    We create a character array `word` of size `n + m - 1` and a boolean array `is_fixed` of the same size. We iterate through `str1`. Whenever we find `str1[i] == 'T'`, we must place `str2` into `word` at the interval `[i, i + m - 1]`. We mark these positions in `is_fixed` as `true`. If we encounter a conflict (i.e., a position is already fixed to a different character), it's impossible to generate a valid string, so we return `""`.

2.  **Phase 2: Greedy Fill**
    After Phase 1, some positions in `word` are fixed. To make the string lexicographically smallest, we should fill all non-fixed positions with the smallest possible character, which is 'a'.

3.  **Phase 3: Verify and Fix 'F' Constraints**
    The `word` we have now is the lexicographically smallest string that satisfies all 'T' constraints. However, it might violate some 'F' constraints. We iterate through `str1` from `i = 0` to `n-1`. If `str1[i] == 'F'`, we check if `word.substring(i, i + m)` is equal to `str2`. 
    If it is, we have a violation. We must modify `word` to break this equality. To maintain the lexicographically smallest result, we should make the smallest possible change at the rightmost possible position. We scan the substring `word[i : i+m]` from right to left (from index `i+m-1` down to `i`). We look for the first character `word[k]` that is not fixed (i.e., `is_fixed[k]` is false) and is not 'z'. If we find such a character, we increment it (`word[k]++`). This change guarantees that the substring is no longer equal to `str2` and has the minimal lexicographical impact. If we cannot find any such character to modify in the window (e.g., all are fixed or are 'z'), then it's impossible to satisfy this 'F' constraint, and we return `""`.

This process ensures that we find the lexicographically smallest valid string because we start with the smallest possible candidate and make minimal necessary changes to satisfy all conditions.
### Algorithm
- Initialize a character array `word` of length `n + m - 1` and a boolean array `is_fixed` of the same length.
- **Phase 1:** Iterate `i` from `0` to `n-1`. If `str1[i] == 'T'`: 
  - For each `j` from `0` to `m-1`, let `k = i + j`.
  - If `is_fixed[k]` is true and `word[k]` is not `str2[j]`, return `""` (conflict).
  - Set `word[k] = str2[j]` and `is_fixed[k] = true`.
- **Phase 2:** Iterate `k` from `0` to `n+m-2`. If `!is_fixed[k]`, set `word[k] = 'a'`.
- **Phase 3:** Iterate `i` from `0` to `n-1`. If `str1[i] == 'F'`: 
  - Check if the substring `word[i : i+m]` equals `str2`.
  - If they are equal, we must fix it:
    - Iterate `k` from `i+m-1` down to `i`.
    - If `!is_fixed[k]` and `word[k] < 'z'`: 
      - Increment `word[k]`. Break the inner loop (over `k`).
    - If the inner loop completes without finding a character to change, return `""` (impossible to fix).
- Finally, convert the `word` array to a string and return it.