Find And Replace in String

Medium

Asked by:

13 views

Topics:

Strings

You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the i^th replacement operation:

Check if the substring sources[i] occurs at index indices[i] in the original string s.
If it does not occur, do nothing.
Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".

Example 2:

Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.

Constraints:

1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indexes[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
s consists of only lowercase English letters.
sources[i] and targets[i] consist of only lowercase English letters.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the lengths of `s`, `indices`, `sources`, and `targets`? Can I assume they are all non-empty?
Can the `indices` array contain duplicate values, and if so, how should overlapping replacements be handled?
If a source string doesn't match the substring in `s` at the corresponding index, should I skip the replacement or is there a default behavior?
What should the output be if no replacements are made? Should I return the original string `s`?
Is it possible for source strings to overlap in the original string `s` after replacements are applied?

Brute Force Solution

Approach

We're given a main string and instructions to find and replace parts of it. The brute force method looks at every possible location in the main string where a replacement might be needed and performs the replacement if it matches the instruction. It methodically checks each position and applies or skips replacements based on direct comparison.

Here's how the algorithm would work step-by-step:

Go through the main string, one position at a time.
At each position, check if there's a replacement instruction that starts at that location.
To check, compare the 'find' part of the instruction to the substring of the main string starting at that position.
If they match, perform the replacement. This means taking out the 'find' part and inserting the 'replace' part in its place.
If they don't match, just move on to the next position in the main string without doing anything.
Continue doing this until you've checked every position in the main string.

Code Implementation

def find_and_replace_in_string_brute_force(main_string, indices, sources, targets):
    modified_string = list(main_string)
    
    for index_in_main_string in range(len(main_string)):
        for i in range(len(indices)):
            if indices[i] == index_in_main_string:
                source_string = sources[i]
                target_string = targets[i]

                # Check if the source string matches the main string at current index
                if main_string[index_in_main_string:index_in_main_string + len(source_string)] == source_string:

                    # Perform the replacement if there is a match
                    for replace_index in range(len(source_string)):
                        modified_string[index_in_main_string + replace_index] = ''

                    modified_string[index_in_main_string] = target_string

                    # Update main_string to reflect the change to prevent overlapping replaces
                    main_string = "".join(modified_string)
                    modified_string = list(main_string)

    return "".join(modified_string)

Big(O) Analysis

Time Complexity

O(n*m*k) – The algorithm iterates through the main string of length n. For each position, it checks if any of the m replacement instructions start at that position. The check involves comparing the 'find' string (of maximum length k) with a substring of the main string. Therefore, the overall time complexity is O(n*m*k), where n is the length of the main string, m is the number of replacement instructions, and k is the maximum length of the 'find' strings. In the worst case, each of the n positions needs to be checked against each of the m replacement instructions involving a comparison of length k.

Space Complexity

O(N) – The provided brute force approach, as described, modifies the string in place. However, performing string modifications in-place in many languages (like Python or Java with immutable strings) effectively creates a new string with each replacement. In the worst-case scenario, where replacements occur frequently, the algorithm might build a completely new string piece by piece. This new string, which is an auxiliary data structure, can grow up to the size of the original string, denoted as N. Therefore, the space complexity is O(N).

Optimal Solution

Approach

We will process the original string by figuring out which replacements need to happen first. We sort the replacements by their starting position to easily apply them in the correct order. This avoids messing up future replacement positions as we change the string.

Here's how the algorithm would work step-by-step:

First, create a way to keep track of all the changes (replacements) we want to make to the original string.
Then, sort these changes based on where they start in the string so we know which change comes first.
Now, go through the changes in order. For each change, check if it's actually valid given the current state of the string. A change would not be valid if an earlier change shifted the location of the current change and the change is no longer valid.
If the change is valid, apply it to the string by replacing the appropriate part with the new text.
Continue doing this for all the planned changes.
In the end, you'll have the final string with all the valid changes applied in the correct order.

Code Implementation

def find_and_replace_in_string(string, indices, sources, targets):
    replacements = []
    for i in range(len(indices)):
        replacements.append((indices[i], sources[i], targets[i]))

    # Sort replacements by starting index
    replacements.sort()

    modified_string = list(string)
    for index, source, target in replacements:
        # Check if the source string matches at the given index
        if string[index:index + len(source)] == source:
            # This replacement is valid, proceed to apply.

            modified_string[index:index + len(source)] = list(target)

    return "".join(modified_string)

Big(O) Analysis

Time Complexity

O(n log n + m * k) – Let n be the number of replacement operations and m be the length of the original string and k be the length of the longest source string. Sorting the replacement operations takes O(n log n) time. After sorting, we iterate through the replacement operations, checking the validity of each replacement by comparing substrings of length k, contributing O(n * k) to the time complexity. Applying the replacements themselves involves string manipulations, which can take O(m) in the worst case if each replacement increases the length of the original string leading to a quadratic string copy cost, but it is considered to be O(n) given amortized string copy costs during append operations to the string buffer. The substring matching takes O(k) in the worst case. Therefore, the overall time complexity is O(n log n + n * k).

Space Complexity

O(K) – The algorithm uses an auxiliary data structure to store the replacements, where K is the number of replacement operations. This data structure stores information about each replacement, such as its starting position, source string, and target string. Therefore, the space required to store this data directly scales with the number of replacements, resulting in O(K) space complexity.

Edge Cases

Case	How to Handle
Empty string	Return the empty string immediately, as there's nothing to modify.
Null input strings or arrays	Throw an IllegalArgumentException or return null/empty string after checking for null inputs.
Empty sources or targets array	Return the original string if either sources or targets array are empty.
Sources and targets arrays have different lengths	Throw an IllegalArgumentException indicating mismatched array lengths.
Overlapping source ranges	Sort the replacements by starting index and process them in order, skipping overlapping ranges or choosing the earliest one.
Source string is not found in the original string	Skip the replacement for that particular source string.
Very large string and numerous replacements	Use StringBuilder for efficient string manipulation to avoid repeated string concatenation.
Indexes array out of bounds	Ensure all indices in the 'indices' array are valid and within the bounds of the original string.

Empty string

How to Handle:

Return the empty string immediately, as there's nothing to modify.

Null input strings or arrays

How to Handle:

Throw an IllegalArgumentException or return null/empty string after checking for null inputs.

Empty sources or targets array

How to Handle:

Return the original string if either sources or targets array are empty.

Sources and targets arrays have different lengths

How to Handle:

Throw an IllegalArgumentException indicating mismatched array lengths.

Overlapping source ranges

How to Handle:

Sort the replacements by starting index and process them in order, skipping overlapping ranges or choosing the earliest one.

Source string is not found in the original string

How to Handle:

Skip the replacement for that particular source string.

Very large string and numerous replacements

How to Handle:

Use StringBuilder for efficient string manipulation to avoid repeated string concatenation.

Indexes array out of bounds

How to Handle:

Ensure all indices in the 'indices' array are valid and within the bounds of the original string.