Skip to main content
Talentd

Match Substring After Replacement - Solution & Explanation

HardArrayHash TableStringString Matching25 min readAsked at: Discord
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive a string s, a pattern sub, and a list of allowed character replacements. Each pair (a, b) means character a in the pattern may be replaced with b when matching. The goal is to determine whether sub can match any substring of s after applying these allowed replacements.

Approach 1: Direct Mapping and Iterative Check (Time: O(n * m), Space: O(k))

Store all replacement rules in a hash-based lookup structure such as HashMap<char, Set<char>>. Each key represents a pattern character and the set contains characters it may transform into. Then iterate through every possible starting index in s. For each index, compare the substring of length m with sub character by character.

At position j, the characters match if either s[i + j] == sub[j] or the mapping allows sub[j] to transform into s[i + j]. If any position fails both checks, break early and move to the next starting index. This approach relies on constant‑time hash table lookups and straightforward string iteration. The early exit significantly reduces average runtime in practice.

Approach 2: Optimized Trie-Based Matching (Time: O(n + m * Σ), Space: O(n * Σ))

A more structured approach builds a trie from substrings of s. Each path in the trie represents a possible sequence of characters from the source string. While matching the pattern, you traverse the trie but allow multiple outgoing edges when replacements are possible.

For each character sub[j], the algorithm considers the direct match and every character reachable through the replacement map. The trie lets you branch efficiently while pruning impossible paths early. This reduces redundant substring comparisons that occur in the naive scan. The technique combines prefix sharing with controlled branching, a common optimization in advanced string matching systems.

This method performs well when the input string is large or when many substring checks would otherwise repeat similar prefix comparisons.

Recommended for interviews: The direct mapping with iterative substring checking is the expected solution. It demonstrates correct modeling of the replacement rules using a hash map and efficient early termination during comparisons. The trie approach shows deeper knowledge of string matching optimizations, but most interviewers expect the hash‑map scanning solution first because it is simpler and already meets typical constraints.

Approach 1: Using Direct Mapping and Iterative Check

This approach involves creating a mapping of characters from `sub` to possible replacements according to the `mappings` array. Then, iterate over all possible substrings of `s` of the length of `sub` and check if any transformation of `sub` matches the current substring of `s`.

We first parse the `mappings` to build a dictionary where each character points to a set of possible replacements (including itself). As we slide a window equal to the size of `sub` over `s`, we check if we can replace `sub` into that substring using our replacements mappings.

In this C solution, we define a boolean 2D array for possible character transformations including self-transformations. For each substring of `s` of the same length as `sub`, we check whether `sub` can be transformed into it. This approach ensures each character can still be a match for the original character itself.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O((s.length - sub.length) * sub.length * |Σ|), where |Σ| is the character set size (here assumed to be 256).
Space Complexity: O(|Σ| * |Σ|) for storing transformation relationships.

Try this approach in the editor →

Approach 2: Optimized Trie-Based Matching

This approach involves building a Trie structure from the substrings of `s` and leveraging potential transformations of the `sub` string to search efficiently within the Trie. Each character in `sub` can be replaced by its possible transformations to find matching paths in the Trie built from `s`.

The Trie allows for quick searching through potential transformations and reduces redundant checks, focusing on viable paths through possible substrings of `s`. It addresses matching patterns effectively by exploring only valid substitution pathways within the Trie structure.

This C solution builds a Trie from substrings of `s`, and employs transformation mapping during Trie traversal using a recursive search function. Each character in the Trie can potentially represent a transformed character from `sub`, facilitating efficient substring checking via the Trie data structure.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m * t), where `n` is the length of `sub`, `m` is the length of `s`, and `t` is the potential mapping transformation choices.
Space Complexity: O(m * n).

Try this approach in the editor →

Approach 3: Hash Table + Enumeration

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

Then we enumerate all substrings of length sub in s, and judge whether the string sub can be obtained by replacement. If it can, return true, otherwise enumerate the next substring.

At the end of the enumeration, it means that sub cannot be obtained by replacing any substring in s, so return false.

The time complexity is O(m times n), and the space complexity is O(C^2). Here, m and n are the lengths of the strings s and sub respectively, and C is the size of the character set.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 4: 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.

The time complexity is O(m times n), and the space complexity is O(C^2).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Direct Mapping and Iterative Check

Time Complexity: O((s.length - sub.length) * sub.length * |Σ|), where |Σ| is the character set size (here assumed to be 256).
Space Complexity: O(|Σ| * |Σ|) for storing transformation relationships.

Optimized Trie-Based Matching

Time Complexity: O(n * m * t), where `n` is the length of `sub`, `m` is the length of `s`, and `t` is the potential mapping transformation choices.
Space Complexity: O(m * n).

Hash Table + Enumeration—
Array + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Mapping and Iterative CheckO(n * m)O(k)General solution. Works well when pattern length is moderate and mapping lookups are constant time.
Trie-Based MatchingO(n + m * Σ)O(n * Σ)Useful when many substring comparisons share prefixes or when repeated matching queries occur.

Video Solution

Leetcode BiWeekly contest 80 Match Substring After Replacement • Prakhar Agrawal • 1,020 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Match Substring After Replacement easy or hard?
Match Substring After Replacement is classified as a Hard problem on LeetCode. The difficulty comes from modeling the replacement rules efficiently and ensuring substring comparisons remain fast even when the input string is large.
Match Substring After Replacement Python/Java solution
In Python or Java, the common approach builds a dictionary or HashMap where each key stores a set of allowed replacement characters. The algorithm scans every starting position in the string and checks whether each character in the pattern matches directly or through the mapping. The implementation remains concise and runs in O(n * m) time.
How to solve Match Substring After Replacement in O(n)?
Strict O(n) matching is difficult because each candidate substring must be validated against the pattern. Optimizations focus on pruning comparisons early or using structures like tries to reuse prefix work. In practice, the O(n * m) hash‑map scanning approach is efficient enough for the given constraints.
What is the best approach for Match Substring After Replacement?
The most practical solution uses a hash map to store allowed replacements and then checks every possible substring of length m in the source string. Each comparison verifies whether characters match directly or through a mapped replacement. This runs in O(n * m) time with O(k) space for the replacement map and is the approach most interviewers expect.
Is Match Substring After Replacement asked at Google/Amazon/Meta?
Problems combining string matching with character transformation rules frequently appear in interviews at companies such as Google, Amazon, and Meta. They test knowledge of hash maps, substring scanning, and efficient comparison strategies under constraints.
What data structure is used in Match Substring After Replacement?
The core data structure is a hash table that maps each character to a set of characters it can transform into. This allows constant‑time validation during substring comparisons. Some optimized solutions also use tries to reduce repeated prefix comparisons in large inputs.
What is the time complexity of Match Substring After Replacement?
The standard solution runs in O(n * m) time where n is the length of the main string and m is the length of the pattern. Each starting index performs a character‑by‑character comparison with constant‑time hash lookups for replacements. Space complexity is O(k) where k is the number of mapping rules.

Ready to solve this problem?

Practice Match Substring After Replacement with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Add and Search Words Data Structure

Next

Number of Subarrays That Match a Pattern II