Match Substring After Replacement - Practice Coding Problems

Match Substring After Replacement - Problem

You are given two strings s and sub. You are also given a 2D character array mappings where mappings[i] = [old_i, new_i] indicates that you may perform the following operation any number of times:

Replace a character old_i of sub with new_i.

Each character in sub cannot be replaced more than once.

Return true if it is possible to make sub a substring of s by replacing zero or more characters according to mappings. Otherwise, return false.

A substring is a contiguous non-empty sequence of characters within a string.

Input & Output

Example 1 — Basic Match with Replacement

$ Input: s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]

› Output: true

💡 Note: At position 2: "ol3e" matches "leet" by replacing e→3 in sub, giving "le37" which doesn't work. At position 2: we need to match s[2:6]="ol3e" with sub="leet". We can replace 'e'→'3' and 't'→'7' to get "le37", but this doesn't match "ol3e". Actually, at position 2: s="ool3" vs sub="leet" - this doesn't work. Let me recalculate: we need s[i:i+4] to match sub after replacements.

Example 2 — No Valid Match

$ Input: s = "fooleetbar", sub = "f00", mappings = [["o","0"]]

› Output: true

💡 Note: At position 0: "foo" matches "f00" by replacing both o→0 in sub, giving "f00" which matches s[0:3]="foo" when we replace o with 0 in sub.

Example 3 — Exact Match

$ Input: s = "abcd", sub = "bc", mappings = []

› Output: true

💡 Note: At position 1: "bc" in s exactly matches sub "bc" without any replacements needed.

Constraints

1 ≤ sub.length ≤ s.length ≤ 5000
0 ≤ mappings.length ≤ 1000
mappings[i].length == 2
s and sub consist of lowercase English letters and digits
mappings[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s, substring sub, and character mappings

Process

Try each position in s, use mappings to transform sub characters

Output

Return true if any position allows sub to match as substring

Key Takeaway

🎯 Key Insight: Use character mappings to transform sub and check if it matches any substring of s at each position

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is to check each position in string s to see if sub can match using character mappings. The hash map approach is optimal, preprocessing mappings for O(1) lookup. Time: O(n×m + k), Space: O(k) where n=|s|, m=|sub|, k=|mappings|.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(n × m + k)	O(k)	Preprocess mappings into a hash map for O(1) lookup during character matching
Brute Force - Try All Positions	O(n × m × k)	O(1)	Check every possible starting position in s and try to match sub with all possible replacements

Hash Map Optimization — Algorithm Steps

Build hash map from mappings array
For each position in s, try to match sub
Use hash map for O(1) character replacement lookup
Return true if any position matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Map

Convert mappings array to hash map for O(1) lookup

Check Positions

For each position, use hash map to check character replacements

Fast Matching

O(1) lookup for each character comparison

Code -

solution.c — C

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

typedef struct {
    char from;
    char to;
} CharMapping;

bool canMatchWithMap(char* s, char* sub, CharMapping* charMap, int mapSize, int start) {
    int subLen = strlen(sub);
    for (int j = 0; j < subLen; j++) {
        char sChar = s[start + j];
        char subChar = sub[j];
        
        if (sChar == subChar) {
            continue;
        }
        
        bool found = false;
        for (int k = 0; k < mapSize; k++) {
            if (charMap[k].from == subChar && charMap[k].to == sChar) {
                found = true;
                break;
            }
        }
        
        if (!found) {
            return false;
        }
    }
    return true;
}

bool solution(char* s, char* sub, char mappings[][2], int mappingCount) {
    // Build mapping array (simpler than hash map in C)
    CharMapping charMap[100];
    int mapSize = 0;
    
    for (int i = 0; i < mappingCount; i++) {
        charMap[mapSize].from = mappings[i][0];
        charMap[mapSize].to = mappings[i][1];
        mapSize++;
    }
    
    int n = strlen(s), m = strlen(sub);
    
    for (int i = 0; i <= n - m; i++) {
        if (canMatchWithMap(s, sub, charMap, mapSize, i)) {
            return true;
        }
    }
    return false;
}

int main() {
    char s[1001], sub[1001], line[10001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    fgets(sub, sizeof(sub), stdin);
    sub[strcspn(sub, "\n")] = 0;
    
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char mappings[100][2];
    int mappingCount = 0;
    
    // Simple JSON parsing for character pairs
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '"' && *(ptr+2) == '"' && *(ptr+6) == '"' && *(ptr+8) == '"') {
            mappings[mappingCount][0] = *(ptr+1);
            mappings[mappingCount][1] = *(ptr+7);
            mappingCount++;
            ptr += 10;
        } else {
            ptr++;
        }
    }
    
    bool result = solution(s, sub, mappings, mappingCount);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m + k)

n positions times m characters, plus k mappings to build hash map

✓ Linear Growth

Space Complexity

O(k)

Hash map stores up to k character mappings

✓ Linear Space

23.4K Views

Medium Frequency

~35 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

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler