We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find And Replace in String

Number: 862

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a 0-indexed string s and three 0-indexed arrays indices, sources, and targets of equal length, perform k replacement operations on s. For each operation, check if the substring sources[i] exactly appears in s starting at indices[i]. If it does, replace that substring with targets[i]. All replacements occur simultaneously (i.e., they do not affect each other’s indexing). The replacements are guaranteed not to overlap.

Key Insights

  • Use a mapping (or dictionary) from index to its respective source and target strings.
  • Process the string in one pass, checking at each index if a replacement should occur.
  • To ensure the original string’s indexing does not get invalidated, either use a pointer scan with conditional skipping or sort replacements in descending order.
  • The problem guarantees non-overlapping replacements.

Space and Time Complexity

Time Complexity: O(n + k * m), where n is the length of s and m is the average length of source strings. Space Complexity: O(n) for the output string (and O(k) additional space for the mapping).

Solution

The solution uses a dictionary (or mapping) to record the indices and corresponding (source, target) pairs. Then iterate through the string with a pointer. At each position, check if there is a replacement defined (i.e., the current index is a key in the mapping). If so, verify that s starting at that index matches the source string. If it matches, append the target string to the result and skip ahead by the length of the source. Otherwise, simply append the current character to the result. This guarantees simultaneous replacements without affecting the indexing for subsequent operations.

Code Solutions

def findReplaceString(s, indices, sources, targets):
    # Create a mapping from indices to the corresponding source and target values.
    index_to_pair = {indices[i]: (sources[i], targets[i]) for i in range(len(indices))}
    
    result = []  # Build the resulting string using a list for efficiency.
    i = 0
    # Iterate through the string using a pointer.
    while i < len(s):
        # Check if the current index has a replacement.
        if i in index_to_pair:
            source, target = index_to_pair[i]
            # If the substring starting at 'i' matches the source, perform replacement.
            if s[i:i+len(source)] == source:
                result.append(target)  # Append the target replacement.
                i += len(source)  # Skip the length of the source substring.
                continue
        # If no replacement occurs, append the current character.
        result.append(s[i])
        i += 1
    # Return the joined result.
    return "".join(result)

# Example usage:
s = "abcd"
indices = [0, 2]
sources = ["a", "cd"]
targets = ["eee", "ffff"]
print(findReplaceString(s, indices, sources, targets))  # Output: "eeebffff"
← Back to All Questions