Match Substring After Replacement - Video Solutions

Problem Overview: You receive a string s, a pattern sub, and a list of allowed character replacements. Each pair (a, b) means character a in the pattern may be replaced with b when matching. The goal is to determine whether sub can match any substring of s after applying these allowed replacements.

Approach 1: Direct Mapping and Iterative Check (Time: O(n * m), Space: O(k))

Store all replacement rules in a hash-based lookup structure such as HashMap<char, Set<char>>. Each key represents a pattern character and the set contains characters it may transform into. Then iterate through every possible starting index in s. For each index, compare the substring of length m with sub character by character.

At position j, the characters match if either s[i + j] == sub[j] or the mapping allows sub[j] to transform into s[i + j]. If any position fails both checks, break early and move to the next starting index. This approach relies on constant‑time hash table lookups and straightforward string iteration. The early exit significantly reduces average runtime in practice.

Approach 2: Optimized Trie-Based Matching (Time: O(n + m * Σ), Space: O(n * Σ))

A more structured approach builds a trie from substrings of s. Each path in the trie represents a possible sequence of characters from the source string. While matching the pattern, you traverse the trie but allow multiple outgoing edges when replacements are possible.

For each character sub[j], the algorithm considers the direct match and every character reachable through the replacement map. The trie lets you branch efficiently while pruning impossible paths early. This reduces redundant substring comparisons that occur in the naive scan. The technique combines prefix sharing with controlled branching, a common optimization in advanced string matching systems.

This method performs well when the input string is large or when many substring checks would otherwise repeat similar prefix comparisons.

Recommended for interviews: The direct mapping with iterative substring checking is the expected solution. It demonstrates correct modeling of the replacement rules using a hash map and efficient early termination during comparisons. The trie approach shows deeper knowledge of string matching optimizations, but most interviewers expect the hash‑map scanning solution first because it is simpler and already meets typical constraints.