Match Substring After Replacement

Match Substring After Replacement

What is this problem about?

In this problem, you are given a string s, a string sub, and a 2D array of character mappings (e.g., ['a', 'b'] means you can replace 'a' with 'b'). You need to determine if it's possible to make sub a contiguous substring of s by replacing some characters in sub according to the provided mappings. You can choose to replace characters or leave them as they are.

Why is this asked in interviews?

This problem evaluates a candidate's ability to optimize string searching when standard equality operators are overridden by custom rules. Interviewers ask it to test your proficiency with Hash Maps and string sliding windows. If you try to generate all possible versions of sub using the mappings, you will trigger an exponential time explosion. You must evaluate the string "in-place".

Algorithmic pattern used

This problem leverages a Hash Set for Mappings combined with a Sliding Window (String Matching) pattern.

1. Convert the 2D mappings array into a Hash Set of strings or a 2D boolean array canReplace[oldChar][newChar] for instant $O(1)$ lookups.
2. Slide a window of length sub.length across the string s.
3. For each window, compare characters of sub against the characters in the window of s. A character matches if sub[j] == s[i+j] OR if canReplace[sub[j]][s[i+j]] is true. If all characters match, return true.

Example explanation

s = "leetcode", sub = "l33t", mappings = [['3', 'e']]. Create boolean map: canReplace['3']['e'] = true. Slide window of size 4 across "leetcode":

• Window at index 0: "leet"
  • sub[0] ('l') vs s[0] ('l'): Match!
  • sub[1] ('3') vs s[1] ('e'): They don't match, BUT canReplace['3']['e'] is true! Valid replacement.
  • sub[2] ('3') vs s[2] ('e'): Valid replacement.
  • sub[3] ('t') vs s[3] ('t'): Match! All characters align using the allowed replacements. The substring matches! Return true.

Common mistakes candidates make

A major pitfall is misunderstanding the direction of the mapping. The prompt specifies you can replace a character in sub with a character in s. The mapping is strictly one-way: old_char -> new_char. Candidates often treat the mappings as bi-directional (like an undirected graph) or attempt to replace characters in s instead of sub, leading to failing edge cases.

Interview preparation tip

For the Match Substring After Replacement coding problem, optimize your mapping lookups. While a HashMap<Character, Set<Character>> works, initializing a boolean[][] map = new boolean[256][256] (handling all ASCII characters) allows for ultra-fast $O(1)$ lookups during the sliding window phase, significantly speeding up the string matching process and showing the interviewer your focus on high performance.