2301. Match Substring After Replacement

Problem Description

The given problem presents the task of determining whether we can make one string (sub) a substring of another string (s) by performing a series of character replacements according to a set of given mappings (mappings). The challenge lies in figuring out if, after performing zero or more of these allowed replacements, sub can be found as a contiguous sequence of characters within s.

Here's what we know about the problem:

• We're given two strings: s (the main string) and sub (the substring we want to match within s).
• mappings is a 2D array of character pairs, where each pair indicates a permissible replacement (old_i, new_i), allowing us to replace old_i in sub with new_i.
• Each character in sub can be replaced only once, ensuring that we cannot keep changing the same character over and over again.
• A "substring" by definition is a contiguous sequence of characters - meaning the characters are adjacent and in order - within a string.

The goal is to return true if sub can be made into a substring of s or false otherwise.

Intuition

The solution approach can be envisioned in a few logical steps. Given that we must find if sub is a substring of s after some amount of character replacements (which are dictated by mappings), the straightforward strategy is to iterate through s and check every possible substring that is the same length as sub.

For each potential match, we iterate over the characters of sub and the corresponding characters of s. We then check two conditions for each character pair:

1. The characters are the same, in which case no replacement is needed.
2. The character from s is in the set of allowed replacements for the corresponding character in sub (as per the mappings).

We maintain a mapping dictionary d where each key is a character from sub, and each value is a set of characters that the key can be replaced with. This allows for quick lookup to check if a character from s is a valid substitute for a character in sub.

If all the characters in a potential match satisfy one of those conditions, we can conclude that it's possible to form sub from that segment of s and return true. If no matches are found after checking all possible segments of s, we return false.

Solution Approach

The implementation of the solution follows a straightforward algorithm which leverages a dictionary to store the mappings for quick lookup, and iterates through the main string s to find a possible match for sub. Here are the steps in detail:

1. First, the algorithm uses a defaultdict from Python's collections module to create a dictionary (d) where each key will reference a set of characters. This defaultdict is a specialized dictionary that initializes a new entry with a default value (in this case, an empty set) if the key is not already present.

2. It then populates this dictionary with the mappings. For each pair (old character, new character) given in the mappings list, the algorithm adds the new character to the set corresponding to the old character.

3. The next step is to iterate through the main string s. The algorithm checks every substring of s that is the same length as sub which is done by using the range for i in range(len(s) - len(sub) + 1). This loop will go over each starting point for a potential substring within s.

4. For each starting index i, the algorithm performs a check to determine if the substring of s starting at i and ending at i + len(sub) can be made to match sub by replacements. This is done by using the all() function combined with a generator expression: all(a == b or a in d[b] for a, b in zip(s[i : i + len(sub)], sub)). This generator expression creates tuples of corresponding characters from the potential substring of s and from sub.

5. Each tuple consists of a character a from s and a character b from sub. The expression checks if a equals b (no replacement needed), or if a is an acceptable replacement for b as per the dictionary d. If all character comparisons satisfy one of these conditions, then the substring of s starting at i is a match for sub, and the function returns true.

6. If no such starting index i is found where sub can be matched in s after all necessary replacements, the algorithm reaches the end of the function and returns false, indicating that it is not possible to make sub a substring of s with the given character replacements.

The solution effectively combines data structure utilization (dictionary of sets for mapping) with the concept of sliding windows (iterating over substrings of s that are of the same length as sub).

Example Walkthrough

Let's illustrate the solution approach with a simple example:

Say we have the main string s as "dogcat", the target substring sub as "dag", and the mappings as [('a', 'o'), ('g', 'c')]. We are to determine if we can make sub a substring of s by using the given character replacements.

Following the solution approach:

1. First, we create a defaultdict to store the mappings. It will look like this after populating it with the given mappings:

   1d = {
   2     'a': {'o'}, 
   3     'g': {'c'}
   4    }

   This tells us that 'a' can be replaced with 'o', and 'g' can be replaced with 'c'.

2. Next, we'll iterate through the string s to find potential substrings that match the length of sub (3 characters). The substrings of s we'll check are "dog", "ogc", and "gca".

3. The first potential match is "dog". We compare it with "dag", the desired sub. We see that:

   • The first characters 'd' match.
   • The second characters 'o' and 'a' do not match, but since 'o' is in the set of allowed characters for 'a' in the dictionary d, this is an acceptable replacement.
   • The third characters 'g' and 'g' match.

   Since all characters are either matching or can be replaced accordingly, this substring of s ("dog") can be made to match sub.

Thus, the function would return true, indicating that "dag" can indeed be made into a substring of "dogcat" by using the allowed character replacements.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the code is mainly determined by the two loops present.

1. Building the dictionary d from the mappings list has a time complexity of O(M), where M is the length of the mappings list. Since each mapping is added once to the dictionary.

2. The second part of the code involves iterating over s and checking whether sub matches any substring of s with respect to the replacement rules given by mappings. The outer loop runs O(N - L + 1) times, where N is the length of s and L is the length of sub. For each iteration, it runs an inner loop over the length of sub, which contributes O(L).

   For each character in the substring of s, the check a == b or a in d[b] is made, which takes O(1) on average (with a good hash function for the underlying dictionary in Python). However, in the worst case, when the hash function has many collisions, this could degrade to O(K), where K is the maximum number of mappings for a single character.

Therefore, the overall worst-case time complexity can be expressed as O(M + (N - L + 1) * L * K). The average case would be O(M + (N - L + 1) * L) assuming constant time dictionary lookups.

Space Complexity

1. The space complexity for the dictionary d is O(M * K), where M is the number of unique original characters in mappings, and K is the average number of replacements for each character.

2. No additional significant space is used in the rest of the code.

Combining these factors, the overall space complexity is O(M * K).

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