Match Substring After Replacement
HardPrompt
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 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 <= 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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a straightforward brute-force method. It iterates through all possible substrings of s that have the same length as sub. For each of these substrings, it checks if sub can be transformed into it by using the allowed mappings. The check for a valid mapping is done by linearly scanning the mappings array each time a replacement is needed.
Algorithm
- Iterate through every possible starting index
ifrom0tos.length() - sub.length(). - For each starting index
i, consider the window ofsof lengthsub.length(), which iss.substring(i, i + sub.length()). - Check if
subcan be transformed into this window. This is done by a nested loop fromj = 0tosub.length() - 1. - Inside the inner loop, compare
sub.charAt(j)withs.charAt(i + j). - If they are not equal, perform a linear scan through the entire
mappingsarray to see if a valid replacement[sub.charAt(j), s.charAt(i + j)]exists. - If no such mapping is found for any character, this window is not a match. Break the inner loop and proceed to the next window in
s. - If the inner loop completes successfully for all characters in
sub, it means a match is found. Returntrue. - If the outer loop finishes without finding any match, return
false.
Walkthrough
The naive brute-force approach involves three nested loops. The outer loop selects a starting position for a potential match in the string s. The second loop iterates through the characters of sub and the corresponding characters in the selected window of s. The third and innermost loop iterates through the mappings array every time a character mismatch is found, to search for a valid replacement rule.
Let m be the length of s, n be the length of sub, and k be the number of mappings. The outer loop runs m - n + 1 times. The second loop runs n times. The innermost loop, in the worst case, runs k times for each character comparison. This leads to a very high time complexity.
class Solution { public boolean matchReplacement(String s, String sub, char[][] mappings) { int m = s.length(); int n = sub.length(); if (n > m) { return false; } for (int i = 0; i <= m - n; i++) { boolean isWindowMatch = true; for (int j = 0; j < n; j++) { char sChar = s.charAt(i + j); char subChar = sub.charAt(j); if (sChar != subChar) { boolean canReplace = false; for (char[] mapping : mappings) { if (mapping[0] == subChar && mapping[1] == sChar) { canReplace = true; break; } } if (!canReplace) { isWindowMatch = false; break; } } } if (isWindowMatch) { return true; } } return false; }}Complexity
Time
O((m - n) * n * k), where `m` is the length of `s`, `n` is the length of `sub`, and `k` is the number of mappings. This is approximately O(m * n * k).
Space
O(1) extra space.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space.
Cons
Extremely inefficient due to the triple nested loop structure.
Will result in a 'Time Limit Exceeded' error for larger inputs as per the given constraints.
This approach improves upon the naive brute-force method by optimizing the lookup of mappings. Before starting the search, we preprocess the mappings array into a hash map. This allows us to check if a character replacement is valid in average constant time, instead of linearly scanning the mappings array each time. The main logic of iterating through windows of s remains the same.
Algorithm
- First, preprocess the
mappingsarray into a more efficient data structure for lookups, such as aHashMap<Character, Set<Character>>. The key will be theoldcharacter, and the value will be a set ofnewcharacters it can be replaced with. - This preprocessing step takes O(k) time, where
kis the number of mappings. - Iterate through every possible starting index
ifrom0tos.length() - sub.length(). - For each starting index
i, check ifsubcan be transformed into the windows.substring(i, i + sub.length()). - In an inner loop, compare
sub.charAt(j)withs.charAt(i + j). - If they are not equal, use the precomputed map to check in O(1) average time if
sub.charAt(j)can be mapped tos.charAt(i + j). - If the check fails, this window is not a match. Break and move to the next window.
- If the inner loop completes, a match is found. Return
true. - If the outer loop completes, no match was found. Return
false.
Walkthrough
The key improvement here is to reduce the time taken for checking if a mapping exists. By converting the list of mappings into a HashMap<Character, Set<Character>>, we can answer the query "can character c1 be replaced by c2?" in O(1) on average. The overall algorithm then becomes a standard sliding window check.
- Preprocessing: Create a
HashMapto store mappings. Iterate throughmappings, and for each[old, new]pair, addnewto the set of characters associated with the keyold. - Sliding Window Search: Iterate from
i = 0tom - n. For eachi, assume the windows[i...i+n-1]is a match. Then, iterate fromj = 0ton-1to verify this assumption. Ifsub.charAt(j)ands.charAt(i+j)are different, consult the hash map. If a valid mapping doesn't exist, the assumption was wrong, so we break and check the next window. If the inner loop finishes without breaking, we've found a valid match and can returntrue.
This approach is efficient enough to pass the given constraints.
import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Set; class Solution { public boolean matchReplacement(String s, String sub, char[][] mappings) { Map<Character, Set<Character>> map = new HashMap<>(); for (char[] mapping : mappings) { map.putIfAbsent(mapping[0], new HashSet<>()); map.get(mapping[0]).add(mapping[1]); } int m = s.length(); int n = sub.length(); for (int i = 0; i <= m - n; i++) { boolean isMatch = true; for (int j = 0; j < n; j++) { char sChar = s.charAt(i + j); char subChar = sub.charAt(j); if (sChar != subChar) { if (!map.containsKey(subChar) || !map.get(subChar).contains(sChar)) { isMatch = false; break; } } } if (isMatch) { return true; } } return false; }}Complexity
Time
O(k + m * n), where `m` is the length of `s`, `n` is the length of `sub`, and `k` is the number of mappings. The `k` comes from preprocessing, and `m*n` from the nested loops.
Space
O(k) or O(A^2) where `k` is the number of mappings and `A` is the alphabet size. This space is used for the hash map.
Trade-offs
Pros
Significantly faster than the naive approach.
Efficient enough for the given constraints.
Relatively straightforward to implement.
Cons
The time complexity is still dependent on the product of the lengths of the two strings (
m*n), which can be slow if both are large.
This highly advanced approach leverages a powerful signal processing algorithm, the Fast Fourier Transform (FFT), to solve the problem in sub-quadratic time. The problem of finding matches for all alignments of sub against s is transformed into a problem of polynomial multiplication. By representing the strings and match conditions as polynomials, we can use FFT to compute their convolution, which gives the match scores for all possible alignments at once.
Algorithm
- Define
match(c1, c2)as a function that returns true ifc1 == c2or ifc1can be mapped toc2. - The problem is to find an index
isuch that the sum ofmatch(sub[j], s[i+j])forjfrom0ton-1is equal ton. - This sum can be computed for all
isimultaneously using convolution, which can be implemented efficiently with the Fast Fourier Transform (FFT). - For each character
cin the alphabet, create two binary polynomials (represented as arrays):P_c(x)forsub, where the coefficient ofx^jis 1 ifsub[j] == c, and 0 otherwise.S'_c(x)fors, where the coefficient ofx^kis 1 ifmatch(c, s[k]), and 0 otherwise.
- Compute the convolution of
S'_c(x)and the reversed version ofP_c(x)for each characterc. - The sum of these convolutions over all characters
cgives a final polynomial (array) where the coefficient at a certain position corresponds to the total match score for that alignment. - If any alignment has a score of
n, a valid substring is found.
Walkthrough
This method is based on a common technique for solving string matching problems with mismatches or wildcards. The core idea is to calculate a score for each possible alignment of the pattern (sub) against the text (s).
Let's define a score score(i) = sum_{j=0}^{n-1} f(sub[j], s[i+j]), where f(c1, c2) is 1 if c1 can be transformed into c2 (either they are equal or a mapping exists), and 0 otherwise. We are looking for an i where score(i) == n.
The calculation of score(i) for all i is a convolution. We can express this sum as:
score(i) = sum_{j=0}^{n-1} sum_{c_1, c_2 in Alphabet} [sub[j]==c_1] * [s[i+j]==c_2] * f(c_1, c_2)[...] is the Iverson bracket.
This can be rearranged and computed efficiently. For each character c_1 in the alphabet, we can compute its total contribution to the score across all alignments. This involves creating a polynomial for sub indicating positions of c_1, and another polynomial for s indicating positions of characters that c_1 can match. The convolution of these two polynomials, calculated via FFT, gives the contribution of c_1. Summing these contributions for all c_1 gives the final scores.
While theoretically superior, the implementation is non-trivial. It requires a robust FFT implementation capable of handling complex numbers and performing polynomial multiplication in the frequency domain. Due to its complexity, it's typically not expected in a standard coding interview but is a powerful tool in competitive programming.
Complexity
Time
O(A * m log m + k), where `A` is the alphabet size, `m` is `s.length`, and `k` is `mappings.length`. This is significantly better than O(m*n) for large `n`.
Space
O(A * m), where `A` is the size of the alphabet and `m` is the length of `s`. This is needed to store the polynomials for convolution.
Trade-offs
Pros
Asymptotically the most efficient approach.
Solves the problem in nearly linear time with respect to the string lengths.
Cons
Extremely complex to implement, especially in a language like Java which lacks a standard FFT library.
High constant factors and space usage might make it slower than the O(m*n) approach for inputs that are not worst-case.
Solutions
Solution
class Solution {public boolean matchReplacement(String s, String sub, char[][] mappings) { Map<Character, Set<Character>> d = new HashMap<>(); for (var e : mappings) { d.computeIfAbsent(e[0], k->new HashSet<>()).add(e[1]); } int m = s.length(), n = sub.length(); for (int i = 0; i < m - n + 1; ++i) { boolean ok = true; for (int j = 0; j < n && ok; ++j) { char a = s.charAt(i + j), b = sub.charAt(j); if (a != b && !d.getOrDefault(b, Collections.emptySet()).contains(a)) { ok = false; } } if (ok) { return true; } } return false; }}class Solution {public: bool matchReplacement(string s, string sub, vector<vector<char>> &mappings) { unordered_map<char, unordered_set<char>> d; for (auto &e : mappings) { d[e[0]].insert(e[1]); } int m = s.size(), n = sub.size(); for (int i = 0; i < m - n + 1; ++i) { bool ok = true; for (int j = 0; j < n && ok; ++j) { char a = s[i + j], b = sub[j]; if (a != b && !d[b].count(a)) { ok = false; } } if (ok) { return true; } } return false; }};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 FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.