Problem Description

You are given two strings s and sub, along with a 2D character array mappings. Each element in mappings is a pair [old_i, new_i] that defines a replacement rule: you can replace character old_i in sub with character new_i.

The task is to determine if you can make sub appear as a substring somewhere in s by applying these replacement rules to characters in sub.

Key constraints to note:

• You can apply any mapping any number of times (including zero times)
• Each character position in sub can only be replaced once (you cannot chain replacements)
• A character in sub can either stay the same or be replaced according to the mappings

For example, if sub = "abc" and you have mappings [['a','x'], ['b','y']], you could transform sub to any of: "abc", "xbc", "ayc", or "xyc".

The function should return true if there exists at least one position in s where a substring matches sub (either directly or after applying valid replacements). Otherwise, return false.

The solution works by:

1. Building a hash table d where each key is a character from sub and the value is a set of all characters it can be replaced with
2. Checking every possible starting position in s for a substring of length equal to sub
3. For each position, verifying if the substring at that position can match sub by checking if each character pair either matches directly (a == b) or can be matched through a valid replacement (a in d[b])

Intuition

The key insight is that we need to check if sub can "match" any substring of s after applying allowed character replacements. Since we're looking for a substring match, we need to check all possible positions in s where sub could potentially fit.

For each potential starting position in s, we need to verify character-by-character if the substring at that position can match sub. A character at position i in the substring matches the corresponding character in sub if:

1. They are already the same character, OR
2. The character in sub can be replaced to match the character in s according to our mappings

To efficiently check if a replacement is valid, we preprocess the mappings into a hash table. For each character that can be replaced (the old character in mappings), we store all possible characters it can become (the new characters). This gives us O(1) lookup time when checking if a replacement is valid.

The sliding window approach naturally emerges: we slide a window of size len(sub) across string s, and at each position, we check if all characters can match. We use the relationship a == b or a in d[b] where a is from s and b is from sub. This checks: "Is a already equal to b, or can b be replaced to become a?"

The beauty of this approach is its simplicity - rather than trying to generate all possible variations of sub (which could be exponential), we simply check each position in s and verify if a match is possible using our replacement rules.

Solution Approach

The solution uses a hash table combined with enumeration to efficiently solve the problem.

Step 1: Building the Mapping Dictionary

d = defaultdict(set)
for a, b in mappings:
    d[a].add(b)

We create a dictionary d where each key represents a character that can be replaced, and the value is a set of all characters it can be replaced with. Using defaultdict(set) ensures that we can safely add replacements without checking if the key exists first. For example, if mappings = [['a','x'], ['a','y'], ['b','z']], then d would be {'a': {'x', 'y'}, 'b': {'z'}}.

Step 2: Enumerate All Possible Starting Positions

for i in range(len(s) - len(sub) + 1):

We iterate through all valid starting positions in string s where a substring of length len(sub) could exist. The range is len(s) - len(sub) + 1 because the last valid starting position is when there are exactly len(sub) characters remaining.

Step 3: Check Character-by-Character Match

if all(a == b or a in d[b] for a, b in zip(s[i : i + len(sub)], sub)):
    return True

For each starting position i, we extract the substring s[i : i + len(sub)] and pair it with sub using zip. For each character pair (a, b) where a comes from s and b comes from sub, we check:

• a == b: The characters already match without any replacement
• a in d[b]: Character b in sub can be replaced with character a according to our mappings

The all() function ensures that every character position satisfies the matching condition. If all characters match, we've found a valid substring and return True.

Step 4: Return Result

If we complete the loop without finding any matching substring, we return False.

Time Complexity: O(n × m) where n is the length of s and m is the length of sub, as we check at most n positions and each check takes O(m) time.

Space Complexity: O(k) where k is the number of mappings, used to store the hash table.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• s = "axxxbc"
• sub = "abc"
• mappings = [['a','x'], ['b','y']]

Step 1: Build the mapping dictionary

We process each mapping to create our dictionary d:

• ['a','x'] → d['a'] = {'x'}
• ['b','y'] → d['b'] = {'y'}

Final dictionary: d = {'a': {'x'}, 'b': {'y'}}

This tells us:

• Character 'a' in sub can be replaced with 'x'
• Character 'b' in sub can be replaced with 'y'
• Character 'c' has no replacements (stays as 'c')

Step 2: Check each possible starting position in s

We need to check positions 0 through 3 (since len(s) - len(sub) + 1 = 6 - 3 + 1 = 4).

Position i = 0: Check substring "axx" against "abc"

• Compare 'a' with 'a': 'a' == 'a' ✓ (direct match)
• Compare 'x' with 'b': 'x' == 'b' ✗ and 'x' in d['b']? → 'x' in {'y'} ✗
• Since not all characters match, continue to next position

Position i = 1: Check substring "xxx" against "abc"

• Compare 'x' with 'a': 'x' == 'a' ✗ and 'x' in d['a']? → 'x' in {'x'} ✓ (can replace 'a' with 'x')
• Compare 'x' with 'b': 'x' == 'b' ✗ and 'x' in d['b']? → 'x' in {'y'} ✗
• Since not all characters match, continue to next position

Position i = 2: Check substring "xxb" against "abc"

• Compare 'x' with 'a': 'x' == 'a' ✗ and 'x' in d['a']? → 'x' in {'x'} ✓ (can replace 'a' with 'x')
• Compare 'x' with 'b': 'x' == 'b' ✗ and 'x' in d['b']? → 'x' in {'y'} ✗
• Since not all characters match, continue to next position

Position i = 3: Check substring "xbc" against "abc"

• Compare 'x' with 'a': 'x' == 'a' ✗ and 'x' in d['a']? → 'x' in {'x'} ✓ (can replace 'a' with 'x')
• Compare 'b' with 'b': 'b' == 'b' ✓ (direct match)
• Compare 'c' with 'c': 'c' == 'c' ✓ (direct match)
• All characters match! Return True

Result: The function returns True because we found that substring "xbc" at position 3 matches "abc" after replacing 'a' with 'x'.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm iterates through all possible starting positions in string s, which gives us m - n + 1 iterations where m = len(s) and n = len(sub). For each starting position, we check if the substring matches by comparing each character pair, which takes O(n) time. The character comparison itself (checking a == b or a in d[b]) is O(1) since we're using a set for lookups. Therefore, the overall time complexity is O((m - n + 1) × n), which simplifies to O(m × n).

Space Complexity: O(C²)

The space is primarily consumed by the dictionary d which stores the mapping relationships. In the worst case, every character in the character set C could map to every other character, resulting in C² possible mappings. Each mapping is stored as a character in a set within the dictionary. Since we're storing at most C sets (one for each possible key character) and each set can contain at most C characters (all possible replacement characters), the space complexity is O(C²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Direction of Replacement

The Problem: A common mistake is confusing which character can replace which. The mappings [old_i, new_i] mean that old_i in sub can be replaced with new_i. Many people incorrectly interpret this as "new_i can replace old_i" and build their mapping dictionary backwards.

Incorrect Implementation:

# WRONG: This reverses the mapping direction
for old_char, new_char in mappings:
    replacement_map[new_char].add(old_char)  # Backwards!

Why This Fails: If you have mapping ['a', 'x'], this means 'a' in sub can become 'x'. So when checking if substring "xyz" in s matches sub = "abc", we need to check if 'x' (from s) can match 'a' (from sub). The correct check is 'x' in replacement_map['a'], not the other way around.

Solution: Always remember that mappings define what characters in sub can be replaced with. Build the dictionary with the character from sub as the key:

# CORRECT: old_char is from sub, new_char is what it can become
for old_char, new_char in mappings:
    replacement_map[old_char].add(new_char)

Pitfall 2: Attempting to Chain Replacements

The Problem: Some might try to apply multiple replacements to the same character position, thinking if 'a' can become 'b' and 'b' can become 'c', then 'a' can become 'c'.

Example Scenario:

mappings = [['a', 'b'], ['b', 'c']]
sub = "a"
s = "c"

Why This is Wrong: The problem explicitly states each character position can only be replaced once. You cannot chain replacements. In the above example, 'a' can only become 'b', not 'c'.

Solution: Only consider direct mappings. Don't compute transitive closures or attempt to chain replacements. The current solution correctly handles this by only checking direct mappings.

Pitfall 3: Modifying sub Instead of Checking Against s

The Problem: Some might try to generate all possible variations of sub and then check if any of them exist in s. This approach becomes exponentially complex.

Inefficient Approach:

# WRONG: Trying to generate all possible variations
def generate_all_variations(sub, mappings):
    # This could create 2^n variations for n characters!
    variations = set()
    # ... complex recursive generation ...

Why This Fails: If sub has length n and each character has k possible replacements, you could have up to (k+1)^n variations to check, making this approach impractical for large inputs.

Solution: The correct approach (as shown in the solution) is to iterate through s and check if each substring can match sub with the allowed replacements. This is much more efficient with O(n × m) complexity.