algoadvance

You are given a string s and an array of indexes, an array of sources, and an array of targets, all of the same length. The indexes array contains the positions in s where the substrings in sources are to be found. You must check if the substring in s starting from the position given in indexes matches the sources string. If it matches, you should replace that substring in s with the corresponding targets string. If it doesn’t match, do nothing.

Finally, return the modified string after all replacements are done.

Example:

Input: s = "abcd", indexes = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"

Constraints:

Clarifying Questions

  1. Can the indices overlap in such a way that they would affect each other’s replacements?
    • Typically, replacements should be distinct, but we will consider non-overlapping replacements for simplicity until explicitly stated otherwise.
  2. Should we continue processing if a source string at a given index does not match?
    • Yes, if the source does not match, we do not replace and continue with others.

Strategy

  1. Create a list to hold the parts of the new string.
  2. Iterate through the given indexes, sources, and targets sorted by the indexes.
    • For each pair (index, source), if the substring of s starting at index matches source, it will be replaced by the corresponding target.
  3. Construct the final string by concatenating parts of s with the appropriate replacements.

Code

def findReplaceString(s, indexes, sources, targets):
    # Create a list to store changes and iterate in sorted order of indexes
    changes = sorted(zip(indexes, sources, targets))

    # Initialize the final output and the last index processed
    result = []
    last_idx = 0

    # Process each change
    for index, source, target in changes:
        # Append the unmodified part of the string
        result.append(s[last_idx:index])
        
        # If the substring matches the source, replace it with the target
        if s[index:index+len(source)] == source:
            result.append(target)
            last_idx = index + len(source)
        else:
            last_idx = index

    # Include any remaining part of the string
    result.append(s[last_idx:])

    # Join the list into a final string and return
    return ''.join(result)

# Test example
s = "abcd"
indexes = [0, 2]
sources = ["a", "cd"]
targets = ["eee", "ffff"]
print(findReplaceString(s, indexes, sources, targets))   # Output: "eeebffff"

Time Complexity

This solution efficiently handles the requirements by processing replacements in the correct order while ensuring non-overlapping and correct application of replacements.

Try our interview co-pilot at AlgoAdvance.com