How to Solve Match Substring After Replacement

This problem requires verifying if one string can become a substring of another after applying character replacements defined in mappings. Use array scanning to generate candidate substrings of the target length and hash lookups to efficiently check if replacements allow a match. GhostInterview guides you through enumerating substrings, mapping characters, and early pruning to reach a correct result quickly.

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

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.

How GhostInterview Helps

• GhostInterview highlights which substrings to scan first and guides through efficient enumeration.
• It helps implement a hash-based replacement check to avoid redundant mapping scans.
• The tool provides step-by-step feedback on enforcing one-time replacement constraints per character.

Topic Pages

• Array
• Hash Table
• String
• String Matching

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.