LeetCode Solutions Blog

Match Substring After Replacement

Number: 2393

Difficulty: Hard

Paid? No

Companies: Discord

Problem Description

Given two strings s and sub along with a list of mappings that allow you to replace a character in sub with a new character (each character in sub can be replaced at most once), determine if it is possible to transform sub (using zero or more allowed replacements) into a substring of s.

Key Insights

For each character in sub, create a set of possible characters it can become (including itself).
The mapping operation is one-time per character index in sub—once replaced, no further changes are allowed for that character.
Use a sliding window in s of length equal to sub and for each candidate window, verify that each character in the window is allowed by the corresponding character’s replacement set.
Precompute the allowed replacements for all characters in sub to optimize the per-window checking.

Space and Time Complexity

Time Complexity: O(n * L) where n = len(s) and L = len(sub). In the worst case, this is acceptable given the constraints. Space Complexity: O(L + M) where L is the length of sub (for storing allowed sets for each character) and M is the number of mappings.

Solution

We first build a mapping dictionary that, for every character in sub, contains a set of possible characters it can be (including itself and any allowed replacements). Then, we slide a window of the same length as sub through s. For every window, we compare each character with the allowed set corresponding to the position in sub. If all characters in the window match the allowed possibilities, we return true. If no matching window is found after checking all possible positions, we return false.

Code Solutions

# Function to determine if sub can be transformed into a substring of s using allowed mappings.
def matchSubstringAfterReplacement(s, sub, mappings):
    n = len(s)
    L = len(sub)
    
    # Build a dictionary of allowed characters for each character in sub.
    # For each character, include the character itself plus any mapped characters.
    allowed = {}
    for ch in sub:
        if ch not in allowed:
            allowed[ch] = set([ch])
        else:
            allowed[ch].add(ch)
    
    # Process mappings: for every mapping, add the 'new' character as allowed replacement for 'old'
    for old, new in mappings:
        # Only update if the old char exists in the allowed mapping (i.e., appears in sub)
        if old in allowed:
            allowed[old].add(new)
    
    # Try every possible contiguous substring of s with the same length as sub.
    for i in range(n - L + 1):
        valid = True
        # For each position in the substring candidate from s:
        for j in range(L):
            ch_sub = sub[j]
            ch_s = s[i + j]
            # Check if ch_s matches any allowed transformation of sub[j]
            if ch_s not in allowed.get(ch_sub, {ch_sub}):
                valid = False
                break
        # If a valid window is found, return true immediately.
        if valid:
            return True
    return False

# Example usage:
s = "fool3e7bar"
sub = "leet"
mappings = [["e","3"], ["t","7"], ["t","8"]]
print(matchSubstringAfterReplacement(s, sub, mappings))  # Expected output: True