Find And Replace in String - Practice Coding Problems

Find And Replace in String - Problem

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.

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

Input & Output

Example 1 — Basic Replacement

$ Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]

› Output: "eeebffff"

💡 Note: At index 0, "a" matches source "a", replace with "eee". At index 2, "cd" matches source "cd", replace with "ffff".

Example 2 — No Match

$ Input: s = "abcd", indices = [0, 2], sources = ["ab", "ec"], targets = ["eee", "ffff"]

› Output: "eeecd"

💡 Note: At index 0, "ab" matches, replace with "eee". At index 2, "cd" ≠ "ec", no replacement.

Example 3 — Multiple Operations

$ Input: s = "vmokgggqzp", indices = [3, 5, 1], sources = ["kg", "ggq", "mo"], targets = ["s", "so", "bfr"]

› Output: "vbfrssozp"

💡 Note: Replace "mo" at index 1 with "bfr", "kg" at index 3 with "s", and "ggq" at index 5 with "so".

Constraints

1 ≤ s.length ≤ 1000
k == indices.length == sources.length == targets.length
1 ≤ k ≤ 100
0 ≤ indices[i] < s.length
1 ≤ sources[i].length, targets[i].length ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

String with replacement specifications

Validate

Check which replacements are valid

Apply

Perform all valid replacements simultaneously

Key Takeaway

🎯 Key Insight: Sort replacements by index descending to avoid position shifts during simultaneous replacements

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to process replacements from right to left to avoid index shifting. Sort valid replacements by position in descending order, then apply them sequentially. Best approach uses sort-first strategy: Time O(k log k + n), Space O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n × k × m)	O(n)	Check each replacement and build result string character by character
Sort by Index	O(k log k + n + km)	O(k + n)	Sort replacements by position and process from right to left

Brute Force — Algorithm Steps

Iterate through each character position
Check if any replacement starts at current position
If match found, add target and skip source length
Otherwise add original character

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Position

Check current character position

Check Replacements

Look for matching replacement at this position

Replace or Keep

Either replace with target or keep original

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s, int* indices, char sources[][100], char targets[][100], int k) {
    char* result = malloc(10000);
    result[0] = '\0';
    int i = 0, len = strlen(s);
    
    while (i < len) {
        int replaced = 0;
        for (int j = 0; j < k; j++) {
            if (indices[j] == i) {
                int sourceLen = strlen(sources[j]);
                if (i + sourceLen <= len && strncmp(s + i, sources[j], sourceLen) == 0) {
                    strcat(result, targets[j]);
                    i += sourceLen;
                    replaced = 1;
                    break;
                }
            }
        }
        if (!replaced) {
            int resultLen = strlen(result);
            result[resultLen] = s[i];
            result[resultLen + 1] = '\0';
            i++;
        }
    }
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int indices[100];
    char sources[100][100];
    char targets[100][100];
    int k = 0;
    
    // Simple parsing for demo
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d %s %s", &indices[i], sources[i], targets[i]);
    }
    
    char* result = solution(s, indices, sources, targets, k);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k × m)

For each of n characters, check k replacements, each requiring m characters for substring comparison

✓ Linear Growth

Space Complexity

O(n)

Result string storage

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler