# Match Substring After Replacement
**Difficulty:** HARD
[External](https://leetcode.com/problems/match-substring-after-replacement)
Canonical: https://scaleengineer.com/dsa/problems/match-substring-after-replacement
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Data structures:** Array, Hash Table, String
---
## Problem
You are given two strings `s` and `sub`. You are also given a 2D character array `mappings` where `mappings[i] = [oldi, newi]` indicates that you may perform the following operation **any** number of times:

* **Replace** a character `oldi` of `sub` with `newi`.

Each character in `sub` **cannot** be replaced more than once.

Return `true` _if it is possible to make_ `sub` _a substring of_ `s` _by replacing zero or more characters according to_ `mappings`. Otherwise, return `false`.

A **substring** is a contiguous non-empty sequence of characters within a string.

**Example 1:**

**Input:** s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
**Output:** true
**Explanation:** Replace the first 'e' in sub with '3' and 't' in sub with '7'.
Now sub = "l3e7" is a substring of s, so we return true.

**Example 2:**

**Input:** s = "fooleetbar", sub = "f00l", mappings = [["o","0"]]
**Output:** false
**Explanation:** The string "f00l" is not a substring of s and no replacements can be made.
Note that we cannot replace '0' with 'o'.

**Example 3:**

**Input:** s = "Fool33tbaR", sub = "leetd", mappings = [["e","3"],["t","7"],["t","8"],["d","b"],["p","b"]]
**Output:** true
**Explanation:** Replace the first and second 'e' in sub with '3' and 'd' in sub with 'b'.
Now sub = "l33tb" is a substring of s, so we return true.

**Constraints:**

* `1 <= sub.length <= s.length <= 5000`
* `0 <= mappings.length <= 1000`
* `mappings[i].length == 2`
* `oldi != newi`
* `s` and `sub` consist of uppercase and lowercase English letters and digits.
* `oldi` and `newi` are either uppercase or lowercase English letters or digits.

# Approaches
## Brute-Force with Linear Scan
This approach uses a straightforward brute-force method. It iterates through all possible substrings of `s` that have the same length as `sub`. For each of these substrings, it checks if `sub` can be transformed into it by using the allowed mappings. The check for a valid mapping is done by linearly scanning the `mappings` array each time a replacement is needed.
**Time:** O((m - n) * n * k), where `m` is the length of `s`, `n` is the length of `sub`, and `k` is the number of mappings. This is approximately O(m * n * k). · **Space:** O(1) extra space.
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Extremely inefficient due to the triple nested loop structure.; Will result in a 'Time Limit Exceeded' error for larger inputs as per the given constraints.
### Explanation
The naive brute-force approach involves three nested loops. The outer loop selects a starting position for a potential match in the string `s`. The second loop iterates through the characters of `sub` and the corresponding characters in the selected window of `s`. The third and innermost loop iterates through the `mappings` array every time a character mismatch is found, to search for a valid replacement rule.

Let `m` be the length of `s`, `n` be the length of `sub`, and `k` be the number of mappings. The outer loop runs `m - n + 1` times. The second loop runs `n` times. The innermost loop, in the worst case, runs `k` times for each character comparison. This leads to a very high time complexity.

```java
class Solution {
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        int m = s.length();
        int n = sub.length();

        if (n > m) {
            return false;
        }

        for (int i = 0; i <= m - n; i++) {
            boolean isWindowMatch = true;
            for (int j = 0; j < n; j++) {
                char sChar = s.charAt(i + j);
                char subChar = sub.charAt(j);

                if (sChar != subChar) {
                    boolean canReplace = false;
                    for (char[] mapping : mappings) {
                        if (mapping[0] == subChar && mapping[1] == sChar) {
                            canReplace = true;
                            break;
                        }
                    }
                    if (!canReplace) {
                        isWindowMatch = false;
                        break;
                    }
                }
            }

            if (isWindowMatch) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- Iterate through every possible starting index `i` from `0` to `s.length() - sub.length()`.
- For each starting index `i`, consider the window of `s` of length `sub.length()`, which is `s.substring(i, i + sub.length())`.
- Check if `sub` can be transformed into this window. This is done by a nested loop from `j = 0` to `sub.length() - 1`.
- Inside the inner loop, compare `sub.charAt(j)` with `s.charAt(i + j)`.
- If they are not equal, perform a linear scan through the entire `mappings` array to see if a valid replacement `[sub.charAt(j), s.charAt(i + j)]` exists.
- If no such mapping is found for any character, this window is not a match. Break the inner loop and proceed to the next window in `s`.
- If the inner loop completes successfully for all characters in `sub`, it means a match is found. Return `true`.
- If the outer loop finishes without finding any match, return `false`.

## Sliding Window with Precomputed Mappings
This approach improves upon the naive brute-force method by optimizing the lookup of mappings. Before starting the search, we preprocess the `mappings` array into a hash map. This allows us to check if a character replacement is valid in average constant time, instead of linearly scanning the mappings array each time. The main logic of iterating through windows of `s` remains the same.
**Time:** O(k + m * n), where `m` is the length of `s`, `n` is the length of `sub`, and `k` is the number of mappings. The `k` comes from preprocessing, and `m*n` from the nested loops. · **Space:** O(k) or O(A^2) where `k` is the number of mappings and `A` is the alphabet size. This space is used for the hash map.
**Pros:** Significantly faster than the naive approach.; Efficient enough for the given constraints.; Relatively straightforward to implement.
**Cons:** The time complexity is still dependent on the product of the lengths of the two strings (`m*n`), which can be slow if both are large.
### Explanation
The key improvement here is to reduce the time taken for checking if a mapping exists. By converting the list of mappings into a `HashMap<Character, Set<Character>>`, we can answer the query "can character `c1` be replaced by `c2`?" in O(1) on average. The overall algorithm then becomes a standard sliding window check.

1.  **Preprocessing:** Create a `HashMap` to store mappings. Iterate through `mappings`, and for each `[old, new]` pair, add `new` to the set of characters associated with the key `old`.
2.  **Sliding Window Search:** Iterate from `i = 0` to `m - n`. For each `i`, assume the window `s[i...i+n-1]` is a match. Then, iterate from `j = 0` to `n-1` to verify this assumption. If `sub.charAt(j)` and `s.charAt(i+j)` are different, consult the hash map. If a valid mapping doesn't exist, the assumption was wrong, so we break and check the next window. If the inner loop finishes without breaking, we've found a valid match and can return `true`.

This approach is efficient enough to pass the given constraints.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        Map<Character, Set<Character>> map = new HashMap<>();
        for (char[] mapping : mappings) {
            map.putIfAbsent(mapping[0], new HashSet<>());
            map.get(mapping[0]).add(mapping[1]);
        }

        int m = s.length();
        int n = sub.length();

        for (int i = 0; i <= m - n; i++) {
            boolean isMatch = true;
            for (int j = 0; j < n; j++) {
                char sChar = s.charAt(i + j);
                char subChar = sub.charAt(j);

                if (sChar != subChar) {
                    if (!map.containsKey(subChar) || !map.get(subChar).contains(sChar)) {
                        isMatch = false;
                        break;
                    }
                }
            }

            if (isMatch) {
                return true;
            }
        }

        return false;
    }
}
```
### Algorithm
- First, preprocess the `mappings` array into a more efficient data structure for lookups, such as a `HashMap<Character, Set<Character>>`. The key will be the `old` character, and the value will be a set of `new` characters it can be replaced with.
- This preprocessing step takes O(k) time, where `k` is the number of mappings.
- Iterate through every possible starting index `i` from `0` to `s.length() - sub.length()`.
- For each starting index `i`, check if `sub` can be transformed into the window `s.substring(i, i + sub.length())`.
- In an inner loop, compare `sub.charAt(j)` with `s.charAt(i + j)`.
- If they are not equal, use the precomputed map to check in O(1) average time if `sub.charAt(j)` can be mapped to `s.charAt(i + j)`.
- If the check fails, this window is not a match. Break and move to the next window.
- If the inner loop completes, a match is found. Return `true`.
- If the outer loop completes, no match was found. Return `false`.

## Advanced Approach: Convolution with FFT
This highly advanced approach leverages a powerful signal processing algorithm, the Fast Fourier Transform (FFT), to solve the problem in sub-quadratic time. The problem of finding matches for all alignments of `sub` against `s` is transformed into a problem of polynomial multiplication. By representing the strings and match conditions as polynomials, we can use FFT to compute their convolution, which gives the match scores for all possible alignments at once.
**Time:** O(A * m log m + k), where `A` is the alphabet size, `m` is `s.length`, and `k` is `mappings.length`. This is significantly better than O(m*n) for large `n`. · **Space:** O(A * m), where `A` is the size of the alphabet and `m` is the length of `s`. This is needed to store the polynomials for convolution.
**Pros:** Asymptotically the most efficient approach.; Solves the problem in nearly linear time with respect to the string lengths.
**Cons:** Extremely complex to implement, especially in a language like Java which lacks a standard FFT library.; High constant factors and space usage might make it slower than the O(m*n) approach for inputs that are not worst-case.
### Explanation
This method is based on a common technique for solving string matching problems with mismatches or wildcards. The core idea is to calculate a score for each possible alignment of the pattern (`sub`) against the text (`s`).

Let's define a score `score(i) = sum_{j=0}^{n-1} f(sub[j], s[i+j])`, where `f(c1, c2)` is 1 if `c1` can be transformed into `c2` (either they are equal or a mapping exists), and 0 otherwise. We are looking for an `i` where `score(i) == n`.

The calculation of `score(i)` for all `i` is a convolution. We can express this sum as:
`score(i) = sum_{j=0}^{n-1} sum_{c_1, c_2 in Alphabet} [sub[j]==c_1] * [s[i+j]==c_2] * f(c_1, c_2)`
where `[...]` is the Iverson bracket.

This can be rearranged and computed efficiently. For each character `c_1` in the alphabet, we can compute its total contribution to the score across all alignments. This involves creating a polynomial for `sub` indicating positions of `c_1`, and another polynomial for `s` indicating positions of characters that `c_1` can match. The convolution of these two polynomials, calculated via FFT, gives the contribution of `c_1`. Summing these contributions for all `c_1` gives the final scores.

While theoretically superior, the implementation is non-trivial. It requires a robust FFT implementation capable of handling complex numbers and performing polynomial multiplication in the frequency domain. Due to its complexity, it's typically not expected in a standard coding interview but is a powerful tool in competitive programming.
### Algorithm
- Define `match(c1, c2)` as a function that returns true if `c1 == c2` or if `c1` can be mapped to `c2`.
- The problem is to find an index `i` such that the sum of `match(sub[j], s[i+j])` for `j` from `0` to `n-1` is equal to `n`.
- This sum can be computed for all `i` simultaneously using convolution, which can be implemented efficiently with the Fast Fourier Transform (FFT).
- For each character `c` in the alphabet, create two binary polynomials (represented as arrays):
    - `P_c(x)` for `sub`, where the coefficient of `x^j` is 1 if `sub[j] == c`, and 0 otherwise.
    - `S'_c(x)` for `s`, where the coefficient of `x^k` is 1 if `match(c, s[k])`, and 0 otherwise.
- Compute the convolution of `S'_c(x)` and the reversed version of `P_c(x)` for each character `c`.
- The sum of these convolutions over all characters `c` gives a final polynomial (array) where the coefficient at a certain position corresponds to the total match score for that alignment.
- If any alignment has a score of `n`, a valid substring is found.

# Solutions
### Java

```java
class Solution {
public
  boolean matchReplacement(String s, String sub, char[][] mappings) {
    Map<Character, Set<Character>> d = new HashMap<>();
    for (var e : mappings) {
      d.computeIfAbsent(e[0], k->new HashSet<>()).add(e[1]);
    }
    int m = s.length(), n = sub.length();
    for (int i = 0; i < m - n + 1; ++i) {
      boolean ok = true;
      for (int j = 0; j < n && ok; ++j) {
        char a = s.charAt(i + j), b = sub.charAt(j);
        if (a != b && !d.getOrDefault(b, Collections.emptySet()).contains(a)) {
          ok = false;
        }
      }
      if (ok) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool matchReplacement(string s, string sub, vector<vector<char>> &mappings) {
    unordered_map<char, unordered_set<char>> d;
    for (auto &e : mappings) {
      d[e[0]].insert(e[1]);
    }
    int m = s.size(), n = sub.size();
    for (int i = 0; i < m - n + 1; ++i) {
      bool ok = true;
      for (int j = 0; j < n && ok; ++j) {
        char a = s[i + j], b = sub[j];
        if (a != b && !d[b].count(a)) {
          ok = false;
        }
      }
      if (ok) {
        return true;
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool: d = defaultdict(set) for a, b in mappings: d[a]. add(b) for i in range(len(s) - len(sub) + 1): if all(a == b or a in d[b] for a, b in zip(s[i: i + len(sub)], sub)): return True return False

```