LeetCode 2301 - Match Substring After Replacement

The problem gives us a string s, a target string sub, and a list of character replacement rules called mappings. Each mapping [old, new] means that a character old inside sub may be replaced with new.

leetcodehardarrayhash-tablestringstring-matching

LeetCode Problem 2301

Difficulty: 🔴 Hard
Topics: Array, Hash Table, String, String Matching

Solution

Problem Understanding

The problem gives us a string s, a target string sub, and a list of character replacement rules called mappings.

Each mapping [old, new] means that a character old inside sub may be replaced with new. The replacement is optional, and every character in sub can be replaced at most once. Importantly, replacements only apply from old to new, not the other way around.

Our task is to determine whether, after applying zero or more valid replacements to characters in sub, the resulting string can appear as a contiguous substring inside s.

The important detail is that replacements are conceptual, we do not actually need to generate all possible transformed versions of sub. Instead, we only need to check whether there exists some alignment between sub and a substring of s where every character matches either:

  1. Directly, meaning sub[i] == s[j]
  2. Through a valid replacement mapping, meaning sub[i] can become s[j]

The constraints are important:

  • s.length and sub.length are at most 5000
  • mappings.length is at most 1000

A brute force solution that generates every possible transformed version of sub would explode combinatorially. Even a moderate number of replaceable characters could produce an enormous number of candidate strings.

However, the string sizes are small enough that checking every possible starting position in s is feasible, as long as each comparison is efficient.

Some important edge cases include:

  • No mappings are provided
  • sub already appears in s without replacements
  • Multiple mappings exist for the same character
  • A character in sub cannot be replaced into the required character
  • Uppercase and lowercase characters are different
  • Digits and letters may both appear
  • Replacement direction matters strictly

For example, if we have mapping ["o", "0"], then o -> 0 is allowed, but 0 -> o is not.

Approaches

Brute Force Approach

A naive approach would attempt to generate every possible transformed version of sub using the replacement mappings.

Suppose a character in sub has multiple possible replacement options. Then every occurrence of that character creates branching possibilities. We could recursively try:

  • Keep the original character
  • Replace it with one of its mapped characters

After generating each possible transformed string, we would check whether it exists as a substring of s.

This approach is correct because it explicitly explores all valid transformed versions of sub. If any transformed version appears in s, the answer is true.

The problem is that this becomes exponentially expensive. If several positions in sub each have multiple replacement choices, the number of generated strings grows explosively.

For example, if 20 characters each have 2 possibilities, we already have:

$$2^{20}$$

possible strings.

That is completely infeasible for the given constraints.

Optimal Approach

The key observation is that we do not need to generate transformed strings at all.

Instead, we can directly compare sub against every substring window of s with the same length.

For every aligned pair of characters:

  • If the characters are equal, the position matches
  • Otherwise, we check whether a replacement mapping allows the character from sub to become the character from s

If every character position matches under these rules, then we found a valid transformed substring.

This works because each character replacement is independent. We never need to track complicated state or sequences of transformations. A position either matches directly, matches via mapping, or fails.

We preprocess the mappings into a hash set for constant time lookup.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Generates all transformed versions of sub
Optimal O((n - m + 1) × m) O(k) Checks each substring window using hash lookups

Where:

  • n = len(s)
  • m = len(sub)
  • k = len(mappings)

Algorithm Walkthrough

  1. Create a hash set to store all valid replacement mappings.

Each mapping is stored as a pair (old_char, new_char). Using a hash set allows constant time lookup during substring comparisons. 2. Iterate through every possible starting position in s.

Since sub has length m, the last valid starting index is:

$$n - m$$

For every starting position, we attempt to match the entire sub. 3. Compare characters one by one.

For every index j inside sub:

  • Let sub_char = sub[j]
  • Let s_char = s[start + j]

The position is valid if either:

  • sub_char == s_char
  • (sub_char, s_char) exists in the mapping set
  1. Stop early on mismatch.

If neither condition holds, the current substring window cannot work, so we immediately move to the next starting position. 5. Return true if an entire window matches.

If all characters in a window satisfy the matching rules, then sub can be transformed into that substring. 6. Return false if no window works.

After checking all possible positions, if none match successfully, then the transformation is impossible.

Why it works

The algorithm checks every possible substring of s that could match sub. For each aligned character pair, it validates exactly the conditions allowed by the problem:

  • Exact equality
  • One valid replacement

Because replacements are independent per character and applied at most once, checking positions independently is sufficient. Therefore, if the algorithm finds a fully matching window, a valid transformed substring exists. If all windows fail, no valid transformation can produce a substring of s.

Python Solution

from typing import List, Set, Tuple

class Solution:
    def matchReplacement(
        self,
        s: str,
        sub: str,
        mappings: List[List[str]]
    ) -> bool:

        allowed: Set[Tuple[str, str]] = set()

        for old_char, new_char in mappings:
            allowed.add((old_char, new_char))

        n = len(s)
        m = len(sub)

        for start in range(n - m + 1):

            match = True

            for j in range(m):

                sub_char = sub[j]
                s_char = s[start + j]

                if sub_char == s_char:
                    continue

                if (sub_char, s_char) not in allowed:
                    match = False
                    break

            if match:
                return True

        return False

The implementation begins by preprocessing all mappings into a hash set called allowed. This lets us check whether a replacement is valid in constant time.

Next, we compute the lengths of s and sub. We then iterate over every possible substring window in s that has the same length as sub.

For each window, we compare characters position by position. If the characters already match, we continue immediately. Otherwise, we check whether the pair exists in the mapping set.

If a mismatch occurs that cannot be repaired through replacement, we stop checking the current window early using break.

If we finish checking an entire window without failure, we immediately return True.

If all windows fail, the function returns False.

Go Solution

func matchReplacement(s string, sub string, mappings [][]byte) bool {
	allowed := make(map[byte]map[byte]bool)

	for _, mapping := range mappings {
		oldChar := mapping[0]
		newChar := mapping[1]

		if allowed[oldChar] == nil {
			allowed[oldChar] = make(map[byte]bool)
		}

		allowed[oldChar][newChar] = true
	}

	n := len(s)
	m := len(sub)

	for start := 0; start <= n-m; start++ {
		match := true

		for j := 0; j < m; j++ {
			subChar := sub[j]
			sChar := s[start+j]

			if subChar == sChar {
				continue
			}

			if allowed[subChar] == nil || !allowed[subChar][sChar] {
				match = false
				break
			}
		}

		if match {
			return true
		}
	}

	return false
}

The Go implementation uses a nested map structure instead of a tuple hash set because Go does not have Python-style tuple hashing built in.

The structure:

map[byte]map[byte]bool

stores all valid replacement relationships.

The rest of the logic mirrors the Python version closely. String indexing in Go operates directly on bytes, which works correctly because the problem guarantees ASCII characters only.

Worked Examples

Example 1

s = "fool3e7bar"
sub = "leet"

mappings = [
    ["e", "3"],
    ["t", "7"],
    ["t", "8"]
]

The mapping set becomes:

Original Replacement
e 3
t 7
t 8

We examine each possible window of length 4.

Start Window Comparison Result
0 fool l != f, fail
1 ool3 l != o, fail
2 ol3e l != o, fail
3 l3e7 valid

Detailed comparison for "l3e7":

sub char window char Valid?
l l direct match
e 3 mapped
e e direct match
t 7 mapped

All positions match, so the answer is true.

Example 2

s = "fooleetbar"
sub = "f00l"

mappings = [["o", "0"]]

The only allowed replacement is:

o -> 0

Not:

0 -> o

Checking substring "fool":

sub char window char Valid?
f f direct match
0 o invalid

The replacement direction is wrong.

No valid window exists, so the answer is false.

Example 3

s = "Fool33tbaR"
sub = "leetd"

Mappings:

Original Replacement
e 3
t 7
t 8
d b
p b

Candidate window:

l33tb

Character comparisons:

sub char window char Valid?
l l direct
e 3 mapped
e 3 mapped
t t direct
d b mapped

Every position matches, so the answer is true.

Complexity Analysis

Measure Complexity Explanation
Time O((n - m + 1) × m) We check every substring window and compare up to m characters
Space O(k) The mapping hash set stores all replacement pairs

Where:

  • n = len(s)
  • m = len(sub)
  • k = len(mappings)

The worst case occurs when every substring window must be checked completely before failing. Since there are n - m + 1 windows and each may require m comparisons, the total running time is quadratic in the worst case.

The space complexity is proportional only to the number of mapping pairs stored in the hash structure.

Test Cases

sol = Solution()

# Provided examples
assert sol.matchReplacement(
    "fool3e7bar",
    "leet",
    [["e", "3"], ["t", "7"], ["t", "8"]]
) is True  # basic mapping success

assert sol.matchReplacement(
    "fooleetbar",
    "f00l",
    [["o", "0"]]
) is False  # replacement direction matters

assert sol.matchReplacement(
    "Fool33tbaR",
    "leetd",
    [["e", "3"], ["t", "7"], ["t", "8"], ["d", "b"], ["p", "b"]]
) is True  # multiple replacements

# Exact substring without mappings
assert sol.matchReplacement(
    "abcdef",
    "bcd",
    []
) is True  # direct substring match

# No possible match
assert sol.matchReplacement(
    "abcdef",
    "xyz",
    []
) is False  # completely different strings

# Single character replacement
assert sol.matchReplacement(
    "a1c",
    "abc",
    [["b", "1"]]
) is True  # one replacement needed

# Multiple mappings for same character
assert sol.matchReplacement(
    "a2c",
    "abc",
    [["b", "1"], ["b", "2"], ["b", "3"]]
) is True  # multiple valid replacements

# Case sensitivity
assert sol.matchReplacement(
    "abc",
    "Abc",
    [["A", "a"]]
) is True  # uppercase replacement

# Entire string match
assert sol.matchReplacement(
    "hello",
    "hello",
    []
) is True  # full string equality

# Mapping exists but wrong direction
assert sol.matchReplacement(
    "abc",
    "a1c",
    [["1", "b"]]
) is False  # cannot reverse mapping

# Minimum size strings
assert sol.matchReplacement(
    "a",
    "a",
    []
) is True  # smallest valid input

# Single character replacement success
assert sol.matchReplacement(
    "z",
    "a",
    [["a", "z"]]
) is True  # single replacement

# Repeated characters
assert sol.matchReplacement(
    "1111",
    "aaaa",
    [["a", "1"]]
) is True  # repeated mapping usage

# Window fails late
assert sol.matchReplacement(
    "abcde",
    "abcf",
    [["f", "e"]]
) is True  # last character replacement
Test Why
Example 1 Standard successful replacement
Example 2 Verifies replacement direction
Example 3 Multiple simultaneous replacements
Exact substring Ensures zero replacements work
No match Confirms proper failure behavior
Single replacement Small simple transformation
Multiple mappings Same source character has many targets
Case sensitivity Uppercase and lowercase treated differently
Entire string Full-string matching
Wrong direction Prevents reverse replacement
Minimum size Smallest valid constraints
Single char replacement One-character transformation
Repeated characters Same mapping used multiple times
Late failure Ensures full window comparison correctness

Edge Cases

One important edge case occurs when no mappings are provided. In this situation, the problem reduces to a normal substring search. A buggy implementation might incorrectly assume replacements are always available. Our solution handles this naturally because the mapping set is simply empty, so only direct character equality succeeds.

Another important edge case is replacement direction. The mapping ["o", "0"] allows o -> 0, but not 0 -> o. A common bug is accidentally treating mappings as bidirectional. Our implementation stores mappings exactly as ordered pairs and only checks whether (sub_char, s_char) exists, preserving the correct directionality.

Repeated characters also create subtle issues. Suppose sub = "aaaa" and every a must transform into 1. A flawed implementation might incorrectly think a mapping can only be used once globally. However, the problem only states that each individual character can be replaced at most once. Different positions may independently apply the same mapping. Our algorithm checks each position independently, so repeated usage works correctly.

Case sensitivity is another potential source of mistakes. Since uppercase and lowercase letters are distinct ASCII characters, "A" and "a" are not interchangeable unless explicitly mapped. Our implementation compares characters exactly as given, so case-sensitive behavior is preserved automatically.