2301. Match Substring After Replacement - Solution

The problem

You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [old_i, new_i] indicates that you may perform the following operation any number of times:

Replace a character old_i of sub with new_i.

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
old_i != new_i
s and sub consist of uppercase and lowercase English letters and digits.
old_i and new_i 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.

Python

def can_transform(s, sub, mappings):
    from collections import defaultdict
    transform_map = defaultdict(set)
    for a, b in mappings:
        transform_map[a].add(b)
    for c in range(48,123):
        transform_map[chr(c)].add(chr(c))  # add identity transformation
    m, n = len(s), len(sub)
    for i in range(m - n + 1):
        if all(s[i+j] in transform_map[sub[j]] for j in range(n)):
            return True
    return False

s = "fool3e7bar"
sub = "leet"
mappings = [['e', '3'], ['t', '7'], ['t', '8']]
print(can_transform(s, sub, mappings))

Java

import java.util.*;

public class Solution {
    public static boolean canTransform(String s, String sub, List<List<Character>> mappings) {
        Map<Character, Set<Character>> map = new HashMap<>();
        for (List<Character> m : mappings) {
            map.computeIfAbsent(m.get(0), k -> new HashSet<>()).add(m.get(1));
        }
        for (char c = '0'; c <= 'z'; ++c) {
            map.computeIfAbsent(c, k -> new HashSet<>()).add(c);
        }
        int n = sub.length();
        int m = s.length();
        for (int i = 0; i <= m - n; ++i) {
            boolean matches = true;
            for (int j = 0; j < n; ++j) {
                char sc = s.charAt(i + j);
                char subc = sub.charAt(j);
                if (!map.getOrDefault(subc, Collections.emptySet()).contains(sc)) {
                    matches = false;
                    break;
                }
            }
            if (matches) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String s = "fool3e7bar";
        String sub = "leet";
        List<List<Character>> mappings = Arrays.asList(
                Arrays.asList('e', '3'), Arrays.asList('t', '7'), Arrays.asList('t', '8')
        );
        System.out.println(canTransform(s, sub, mappings));
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

bool canTransform(string s, string sub, vector<vector<char>>& mappings) {
    unordered_map<char, unordered_set<char>> map;
    for (auto& m : mappings) {
        map[m[0]].insert(m[1]);
    }
    for (char c = '0'; c <= 'z'; ++c) { // assume all alphanumeric
        map[c].insert(c);
    }
    for (int i = 0; i <= s.length() - sub.length(); ++i) {
        bool match = true;
        for (int j = 0; j < sub.length(); ++j) {
            if (map[sub[j]].find(s[i + j]) == map[sub[j]].end()) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

int main() {
    string s = "fool3e7bar";
    string sub = "leet";
    vector<vector<char>> mappings = {{'e', '3'}, {'t', '7'}, {'t', '8'}};
    cout << (canTransform(s, sub, mappings) ? "true" : "false") << endl;
    return 0;
}

JavaScript

function canTransform(s, sub, mappings) {
    const map = {};
    mappings.forEach(([a, b]) => {
        if (!map[a]) map[a] = new Set();
        map[a].add(b);
    });
    for (let i = 0; i <= s.length - sub.length; i++) {
        let matches = true;
        for (let j = 0; j < sub.length; j++) {
            const chSub = sub[j];
            const chS = s[i + j];
            if (map[chSub] && map[chSub].has(chS) || chSub === chS) continue;
            matches = false;
            break;
        }
        if (matches) return true;
    }
    return false;
}

console.log(canTransform("fool3e7bar", "leet", [['e', '3'], ['t', '7'], ['t', '8']]))

#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#define MAX_CHAR 256

bool canTransform(char* sub, char* s, char* mappings[][2], int mappingsSize) {
    int n = strlen(sub);
    int m = strlen(s);
    bool map[MAX_CHAR][MAX_CHAR] = {false};
    for (int i = 0; i < mappingsSize; ++i) {
        map[(int)mappings[i][0][0]][(int)mappings[i][1][0]] = true;
    }
    for (int i = 0; i < MAX_CHAR; ++i) {
        map[i][i] = true;
    }
    for (int start = 0; start <= m - n; ++start) {
        bool match = true;
        for (int j = 0; j < n; ++j) {
            if (!map[(int)sub[j]][(int)s[start + j]]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

int main() {
    char* s = "fool3e7bar";
    char* sub = "leet";
    char* mappings[3][2] = {{"e", "3"}, {"t", "7"}, {"t", "8"}};
    bool result = canTransform(sub, s, mappings, 3);
    printf(result ? "true\n" : "false\n");
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static bool CanTransform(string s, string sub, List<(char, char)> mappings) {
        var map = new Dictionary<char, HashSet<char>>();
        foreach (var m in mappings) {
            if (!map.ContainsKey(m.Item1)) map[m.Item1] = new HashSet<char>();
            map[m.Item1].Add(m.Item2);
        }
        for (char c = '0'; c <= 'z'; c++) {
            if (!map.ContainsKey(c)) map[c] = new HashSet<char>();
            map[c].Add(c);
        }
        int m = s.Length, n = sub.Length;
        for (int i = 0; i <= m - n; i++) {
            bool match = true;
            for (int j = 0; j < n; j++) {
                if (!map[sub[j]].Contains(s[i + j])) {
                    match = false;
                    break;
                }
            }
            if (match) return true;
        }
        return false;
    }

    public static void Main() {
        string s = "fool3e7bar";
        string sub = "leet";
        var mappings = new List<(char, char)> { ('e', '3'), ('t', '7'), ('t', '8') };
        Console.WriteLine(CanTransform(s, sub, mappings));
    }
}

This Python implementation uses a dictionary of sets to manage possible transformation characters for each character in `sub`. The existence of a valid transformation for each character in `sub` against a substring of `s` is verified iteratively using Python's range and set membership operations.

Complexity

Time Complexity: O((s.length - sub.length) * sub.length).
Space Complexity: O(|Σ|^2).

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.

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Solution:
    def insert(self, root, key):
        node = root
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, root, key, index, transform_map):
        if index == len(key):
            return root.is_end_of_word
        if key[index] in transform_map:
            for replacement in transform_map[key[index]]:
                if replacement in root.children:
                    if self.search(root.children[replacement], key, index + 1, transform_map):
                        return True
        return False

    def can_transform(self, s, sub, mappings):
        root = TrieNode()
        for i in range(len(s) - len(sub) + 1):
            self.insert(root, s[i:i + len(sub)])
        transform_map = {chr(c): {chr(c)} for c in range(48, 123)}
        for old, new in mappings:
            if old not in transform_map:
                transform_map[old] = {old}
            transform_map[old].add(new)
        return self.search(root, sub, 0, transform_map)

s = "fool3e7bar"
sub = "leet"
mappings = [['e', '3'], ['t', '7'], ['t', '8']]
solution = Solution()
print(solution.can_transform(s, sub, mappings))

Java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

public class Solution {
    private void insert(TrieNode root, String key) {
        TrieNode node = root;
        for (char ch : key.toCharArray()) {
            node = node.children.computeIfAbsent(ch, k -> new TrieNode());
        }
        node.isEndOfWord = true;
    }
    
    private boolean search(TrieNode root, String key, int index, Map<Character, Set<Character>> map) {
        if (index == key.length()) return root.isEndOfWord;
        char ch = key.charAt(index);
        if (map.containsKey(ch)) {
            for (char replacement : map.get(ch)) {
                TrieNode child = root.children.get(replacement);
                if (child != null && search(child, key, index + 1, map)) 
                    return true;
            }
        }
        return false;
    }
    
    public boolean canTransform(String s, String sub, List<List<Character>> mappings) {
        TrieNode root = new TrieNode();
        for (int i = 0; i <= s.length() - sub.length(); i++) {
            insert(root, s.substring(i, i + sub.length()));
        }
        Map<Character, Set<Character>> map = new HashMap<>();
        for (List<Character> m : mappings) {
            map.computeIfAbsent(m.get(0), k -> new HashSet<>()).add(m.get(1));
        }
        for (char c = '0'; c <= 'z'; c++) map.computeIfAbsent(c, k -> new HashSet<>()).add(c);
        return search(root, sub, 0, map);
    }

    public static void main(String[] args) {
        String s = "fool3e7bar";
        String sub = "leet";
        List<List<Character>> mappings = Arrays.asList(
                Arrays.asList('e', '3'), Arrays.asList('t', '7'), Arrays.asList('t', '8')
        );
        Solution solution = new Solution();
        System.out.println(solution.canTransform(s, sub, mappings));
    }
}

C++

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

struct TrieNode {
    TrieNode* children[256] = {};
    bool isEndOfWord = false;
};

void insert(TrieNode* root, const string& key) {
    TrieNode* node = root;
    for (char ch : key) {
        if (!node->children[ch]) node->children[ch] = new TrieNode();
        node = node->children[ch];
    }
    node->isEndOfWord = true;
}

bool search(TrieNode* root, const string& key, int index, unordered_map<char, unordered_set<char>>& map) {
    if (index == key.length()) return root->isEndOfWord;
    char ch = key[index];
    if (map.count(ch)) {
        for (char replacement : map[ch]) {
            if (root->children[replacement] && search(root->children[replacement], key, index + 1, map)) 
                return true;
        }
    }
    return false;
}

bool canTransform(const string& s, const string& sub, vector<pair<char, char>>& mappings) {
    TrieNode* root = new TrieNode();
    for (int i = 0; i <= s.size() - sub.size(); ++i) {
        insert(root, s.substr(i, sub.size()));
    }
    unordered_map<char, unordered_set<char>> map;
    for (auto& m : mappings) map[m.first].insert(m.second);
    for (char c = '0'; c <= 'z'; ++c) map[c].insert(c);
    return search(root, sub, 0, map);
}

int main() {
    string s = "fool3e7bar";
    string sub = "leet";
    vector<pair<char, char>> mappings = {{'e', '3'}, {'t', '7'}, {'t', '8'}};
    cout << (canTransform(s, sub, mappings) ? "true" : "false") << endl;
    return 0;
}

JavaScript

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

function insert(root, key) {
    let node = root;
    for (let char of key) {
        if (!node.children[char]) node.children[char] = new TrieNode();
        node = node.children[char];
    }
    node.isEndOfWord = true;
}

function search(root, key, index, map) {
    if (index === key.length) return root.isEndOfWord;
    if (map[key[index]]) {
        for (let replacement of map[key[index]]) {
            if (root.children[replacement] && search(root.children[replacement], key, index + 1, map))
                return true;
        }
    }
    return false;
}

function canTransform(s, sub, mappings) {
    const root = new TrieNode();
    for (let i = 0; i <= s.length - sub.length; i++) {
        insert(root, s.substring(i, i + sub.length));
    }
    const map = {};
    for (let c = 48; c <= 122; c++) {
        map[String.fromCharCode(c)] = new Set([String.fromCharCode(c)]);
    }
    for (let [a, b] of mappings) {
        if (!map[a]) map[a] = new Set();
        map[a].add(b);
    }
    return search(root, sub, 0, map);
}

console.log(canTransform("fool3e7bar", "leet", [['e', '3'], ['t', '7'], ['t', '8']]));

#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define ALPHABET_SIZE 256

struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    bool endOfWord;
};

struct TrieNode* getNode() {
    struct TrieNode* pNode = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    pNode->endOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
    return pNode;
}

void insert(struct TrieNode* root, char* key) {
    struct TrieNode* nodePtr = root;
    for (int level = 0; level < strlen(key); level++) {
        int index = key[level];
        if (!nodePtr->children[index])
            nodePtr->children[index] = getNode();
        nodePtr = nodePtr->children[index];
    }
    nodePtr->endOfWord = true;
}

bool search(struct TrieNode* root, char* key, bool map[ALPHABET_SIZE][ALPHABET_SIZE]) {
    if (!*key) return root->endOfWord;
    struct TrieNode* nodePtr = root;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (map[(int)(*key)][i] && nodePtr->children[i]) {
            if (search(nodePtr->children[i], key + 1, map))
                return true;
        }
    }
    return false;
}

bool canTransform(char* sub, char* s, char* mappings[][2], int mappingsSize) {
    struct TrieNode* root = getNode();
    int subLen = strlen(sub);
    int sLen = strlen(s);
    // Insert all substrings of s into Trie:
    for (int i = 0; i <= sLen - subLen; ++i) {
        char buffer[subLen + 1];
        strncpy(buffer, s + i, subLen);
        buffer[subLen] = '\0';
        insert(root, buffer);
    }
    // Prepare the mapping
    bool map[ALPHABET_SIZE][ALPHABET_SIZE] = {false};
    for (int i = 0; i < mappingsSize; ++i) {
        map[(int)mappings[i][0][0]][(int)mappings[i][1][0]] = true;
    }
    for (int i = 0; i < ALPHABET_SIZE; ++i) {
        map[i][i] = true;
    }
    // Search with modifications
    bool result = search(root, sub, map);
    // Free Trie Nodes omitted for brevity
    return result;
}

int main() {
    char* s = "fool3e7bar";
    char* sub = "leet";
    char* mappings[3][2] = {{"e", "3"}, {"t", "7"}, {"t", "8"}};
    bool result = canTransform(sub, s, mappings, 3);
    printf(result ? "true\n" : "false\n");
    return 0;
}

using System;
using System.Collections.Generic;

class TrieNode {
    public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
    public bool IsEndOfWord = false;
}

class Solution {
    public void Insert(TrieNode root, string key) {
        TrieNode node = root;
        foreach (var ch in key) {
            if (!node.Children.ContainsKey(ch))
                node.Children[ch] = new TrieNode();
            node = node.Children[ch];
        }
        node.IsEndOfWord = true;
    }

    public bool Search(TrieNode root, string key, int index, Dictionary<char, HashSet<char>> map) {
        if (index == key.Length) return root.IsEndOfWord;
        if (map.ContainsKey(key[index])) {
            foreach (var replacement in map[key[index]]) {
                if (root.Children.ContainsKey(replacement)) {
                    if (Search(root.Children[replacement], key, index + 1, map))
                        return true;
                }
            }
        }
        return false;
    }

    public bool CanTransform(string s, string sub, List<(char, char)> mappings) {
        TrieNode root = new TrieNode();
        for (int i = 0; i <= s.Length - sub.Length; i++)
            Insert(root, s.Substring(i, sub.Length));
        Dictionary<char, HashSet<char>> map = new Dictionary<char, HashSet<char>>();
        foreach (var (oldChar, newChar) in mappings) {
            if (!map.ContainsKey(oldChar))
                map[oldChar] = new HashSet<char>();
            map[oldChar].Add(newChar);
        }
        for (int c = '0'; c <= 'z'; c++) {
            if (!map.ContainsKey((char)c))
                map[(char)c] = new HashSet<char>();
            map[(char)c].Add((char)c);
        }
        return Search(root, sub, 0, map);
    }

    static void Main() {
        string s = "fool3e7bar";
        string sub = "leet";
        var mappings = new List<(char, char)> { ('e', '3'), ('t', '7'), ('t', '8') };
        Solution solution = new Solution();
        Console.WriteLine(solution.CanTransform(s, sub, mappings));
    }
}

The Python code employs a Trie to track substrings of `s`, leveraging mappings to allow potential character substitutions in `sub`. The search function processes transformations recursively to determine matches within the Trie, enhancing pattern checking efficacy.

Complexity

Time Complexity: O(n * m * t), where `n` is the length of `sub`, `m` is the length of `s`, and `t` is influenced by the extent of transformations available.
Space Complexity: O(n * m).

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.

func matchReplacement(s string, sub string, mappings [][]byte) bool {
	d := map[byte]map[byte]bool{}
	for _, e := range mappings {
		if d[e[0]] == nil {
			d[e[0]] = map[byte]bool{}
		}
		d[e[0]][e[1]] = true
	}
	for i := 0; i < len(s)-len(sub)+1; i++ {
		ok := true
		for j := 0; j < len(sub) && ok; j++ {
			a, b := s[i+j], sub[j]
			if a != b && !d[b][a] {
				ok = false
			}
		}
		if ok {
			return true
		}
	}
	return false
}

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).

func matchReplacement(s string, sub string, mappings [][]byte) bool {
	d := [128][128]bool{}
	for _, e := range mappings {
		d[e[0]][e[1]] = true
	}
	for i := 0; i < len(s)-len(sub)+1; i++ {
		ok := true
		for j := 0; j < len(sub) && ok; j++ {
			a, b := s[i+j], sub[j]
			if a != b && !d[b][a] {
				ok = false
			}
		}
		if ok {
			return true
		}
	}
	return false
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Direct Mapping and Iterative Check	Time Complexity: O((s.length - sub.length) * sub.length). Space Complexity: O(\|Σ\|^2).
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 influenced by the extent of transformations available. Space Complexity: O(n * m).
Hash Table + Enumeration	–
Array + Enumeration	–

Complexity analysis

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

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.

Match Substring After Replacement solution and explanation

The problem

Approach overview

Approach 1: Using Direct Mapping and Iterative Check

Approach 2: Optimized Trie-Based Matching

Approach 3: Hash Table + Enumeration

Approach 4: Array + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Match Substring After Replacement solution and explanation

The problem

Approach overview

Approach 1: Using Direct Mapping and Iterative Check

Approach 2: Optimized Trie-Based Matching

Approach 3: Hash Table + Enumeration

Approach 4: Array + Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems