Match Substring After Replacement
HardUpdated: Aug 2, 2025
Practice on:
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
oldiofsubwithnewi.
Each character in sub cannot be replaced more than once.
Return true if it is possible to makesub a substring ofs by replacing zero or more characters according tomappings. Otherwise, return
false.
A substring is a contiguous non-empty sequence of characters within a string.
Examples
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 <= 50000 <= mappings.length <= 1000mappings[i].length == 2oldi != newisandsubconsist of uppercase and lowercase English letters and digits.oldiandnewiare either uppercase or lowercase English letters or digits.
Solution
Method 1 – Sliding Window with Replacement Mapping
Intuition
We want to check if sub can be transformed (using the allowed mappings) into any substring of s. For each window in s of length len(sub), we try to match sub to the window, allowing each character in sub to be replaced at most once according to the mapping. We use a mapping set for fast lookup.
Approach
- Build a set of allowed replacements from
mappingsfor O(1) lookup. - For each window of length
len(sub)ins:- For each character in
sub, check if it matches the corresponding character ins, or if it can be replaced (using the mapping) to match. - If all characters match for a window, return
true.
- For each character in
- If no window matches, return
false.
Code
C++
class Solution {
public:
bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
unordered_map<char, unordered_set<char>> mp;
for (auto& m : mappings) mp[m[0]].insert(m[1]);
int n = s.size(), m = sub.size();
for (int i = 0; i + m <= n; ++i) {
bool ok = true;
for (int j = 0; j < m; ++j) {
if (s[i+j] == sub[j]) continue;
if (!mp.count(sub[j]) || !mp[sub[j]].count(s[i+j])) {
ok = false;
break;
}
}
if (ok) return true;
}
return false;
}
};
Go
func matchReplacement(s string, sub string, mappings [][]byte) bool {
mp := map[byte]map[byte]bool{}
for _, m := range mappings {
if mp[m[0]] == nil {
mp[m[0]] = map[byte]bool{}
}
mp[m[0]][m[1]] = true
}
n, mlen := len(s), len(sub)
for i := 0; i+mlen <= n; i++ {
ok := true
for j := 0; j < mlen; j++ {
if s[i+j] == sub[j] {
continue
}
if mp[sub[j]] == nil || !mp[sub[j]][s[i+j]] {
ok = false
break
}
}
if ok {
return true
}
}
return false
}
Java
class Solution {
public boolean matchReplacement(String s, String sub, char[][] mappings) {
Map<Character, Set<Character>> mp = new HashMap<>();
for (char[] m : mappings) {
mp.computeIfAbsent(m[0], k -> new HashSet<>()).add(m[1]);
}
int n = s.length(), m = sub.length();
for (int i = 0; i + m <= n; i++) {
boolean ok = true;
for (int j = 0; j < m; j++) {
if (s.charAt(i+j) == sub.charAt(j)) continue;
if (!mp.containsKey(sub.charAt(j)) || !mp.get(sub.charAt(j)).contains(s.charAt(i+j))) {
ok = false;
break;
}
}
if (ok) return true;
}
return false;
}
}
Kotlin
class Solution {
fun matchReplacement(s: String, sub: String, mappings: Array<CharArray>): Boolean {
val mp = mutableMapOf<Char, MutableSet<Char>>()
for (m in mappings) mp.getOrPut(m[0]) { mutableSetOf() }.add(m[1])
val n = s.length
val mlen = sub.length
for (i in 0..n-mlen) {
var ok = true
for (j in 0 until mlen) {
if (s[i+j] == sub[j]) continue
if (!mp.containsKey(sub[j]) || !mp[sub[j]]!!.contains(s[i+j])) {
ok = false
break
}
}
if (ok) return true
}
return false
}
}
Python
class Solution:
def matchReplacement(self, s: str, sub: str, mappings: list[list[str]]) -> bool:
mp = {a: set() for a, _ in mappings}
for a, b in mappings:
mp[a].add(b)
n, m = len(s), len(sub)
for i in range(n - m + 1):
ok = True
for j in range(m):
if s[i+j] == sub[j]:
continue
if sub[j] not in mp or s[i+j] not in mp[sub[j]]:
ok = False
break
if ok:
return True
return False
Rust
impl Solution {
pub fn match_replacement(s: String, sub: String, mappings: Vec<Vec<char>>) -> bool {
use std::collections::{HashMap, HashSet};
let mut mp: HashMap<char, HashSet<char>> = HashMap::new();
for m in mappings {
mp.entry(m[0]).or_default().insert(m[1]);
}
let n = s.len();
let m = sub.len();
let s_chars: Vec<char> = s.chars().collect();
let sub_chars: Vec<char> = sub.chars().collect();
for i in 0..=n-m {
let mut ok = true;
for j in 0..m {
if s_chars[i+j] == sub_chars[j] {
continue;
}
if !mp.get(&sub_chars[j]).map_or(false, |set| set.contains(&s_chars[i+j])) {
ok = false;
break;
}
}
if ok {
return true;
}
}
false
}
}
TypeScript
class Solution {
matchReplacement(s: string, sub: string, mappings: string[][]): boolean {
const mp = new Map<string, Set<string>>();
for (const [a, b] of mappings) {
if (!mp.has(a)) mp.set(a, new Set());
mp.get(a)!.add(b);
}
const n = s.length, m = sub.length;
for (let i = 0; i + m <= n; i++) {
let ok = true;
for (let j = 0; j < m; j++) {
if (s[i+j] === sub[j]) continue;
if (!mp.has(sub[j]) || !mp.get(sub[j])!.has(s[i+j])) {
ok = false;
break;
}
}
if (ok) return true;
}
return false;
}
}
Complexity
- ⏰ Time complexity:
O(n*m), wherenis the length ofsandmis the length ofsub, as we check every window. - 🧺 Space complexity:
O(k), wherekis the number of mappings, for the mapping set.