#2301

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Match Substring After Replacement

Determine if a target substring can appear in a string after optional character replacements using given mappings efficiently.

array hash table string string matching

Problem Statement

Given two strings s and sub, and a list of mappings where each mapping [oldi, newi] means oldi in sub can be replaced with newi, determine if sub can be transformed into a substring of s. Each character in sub can be replaced at most once according to the mappings.

Return true if it is possible to make sub a substring of s by performing zero or more allowed replacements. Otherwise, return false. All replacements are one-way and must follow the provided mapping rules exactly.

Examples

Example 1

Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]

Output: true

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

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

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.

Solution Approach

Enumerate Substrings

Generate all substrings of s that have the same length as sub. This ensures each candidate substring can potentially match after replacements. Early exit if the substring matches without replacements.

Use Hash Lookup for Mappings

Build a hash table from the mappings to quickly check allowed replacements. For each character in sub, verify if it matches the corresponding character in the candidate substring or if a replacement exists. This prevents repeated linear scans over the mappings.

Check Replacement Constraints

Ensure no character in sub is replaced more than once and that replacements follow the mappings exactly. Track replacements used per candidate substring to enforce constraints and validate the match before returning true.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on scanning all substrings of length sub.length in s and checking each character with hash lookups, giving O(s.length * sub.length) in worst-case. Space complexity is O(mappings.length) for the hash table plus O(sub.length) for tracking replacements.

What Interviewers Usually Probe

Candidate should recognize the need to scan all substrings of matching length.
Efficient hash-based mapping check is expected to avoid nested loops over mappings.
Proper handling of one-time replacement per character is crucial for correctness.

Common Pitfalls or Variants

Common pitfalls

Replacing a character more than once violates the problem constraint and leads to false positives.
Ignoring case sensitivity in s or sub can produce incorrect matches.
Failing to check all substrings of s of length sub.length may miss valid matches.

Follow-up variants

Allow multiple replacements per character in sub, changing the replacement tracking logic.
Consider mappings that are bi-directional, requiring a different hash lookup strategy.
Check if sub can match s after removing certain characters instead of replacements.

FAQ

What pattern does Match Substring After Replacement follow?

It follows an array scanning plus hash lookup pattern, enumerating all substrings of s and checking replacements efficiently.

Can a character in sub be replaced multiple times?

No, each character in sub can be replaced at most once according to the mappings.

How do I handle case sensitivity in this problem?

Matches are case-sensitive. Ensure s, sub, and mappings are compared with exact character casing.

What if no replacements are needed?

If sub is already a substring of s, return true immediately without using mappings.

Are the mappings one-way or bi-directional?

Mappings are one-way; only oldi can be replaced by newi, never the reverse.

terminal

Solution

Solution 1: Hash Table + Enumeration

First, we use a hash table $d$ to record the set of characters that each character can be replaced with.

1

2

3

4

5

6

7

8

9

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

Solution 2: Array + Enumeration

Since the character set only contains uppercase and lowercase English letters and numbers, we can directly use a $128 \times 128$ array $d$ to record the set of characters that each character can be replaced with.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#2306 naming a company #2284 sender with largest word count #2273 find resultant array after removing anagrams