Stamping The Sequence - Practice Coding Problems

Stamping The Sequence - Problem

You are given two strings stamp and target. Initially, there is a string s of length target.length with all s[i] == '?'.

In one turn, you can place stamp over s and replace every letter in the s with the corresponding letter from stamp. For example, if stamp = "abc" and target = "abcba", then s is "?????" initially. In one turn you can:

place stamp at index 0 of s to obtain "abc??"
place stamp at index 1 of s to obtain "?abc?"
place stamp at index 2 of s to obtain "??abc"

Note that stamp must be fully contained in the boundaries of s in order to stamp (i.e., you cannot place stamp at index 3 of s).

We want to convert s to target using at most 10 * target.length turns. Return an array of the index of the left-most letter being stamped at each turn. If we cannot obtain target from s within 10 * target.length turns, return an empty array.

Input & Output

Example 1 — Basic Case

$ Input: stamp = "abc", target = "ababc"

› Output: [0,2]

💡 Note: Start with "?????". Stamp at position 0: "abc??". Stamp at position 2: "ababc" matches target.

Example 2 — Single Stamp

$ Input: stamp = "abc", target = "abc"

› Output: [0]

💡 Note: Target matches stamp exactly, so one stamp at position 0 creates the target.

Example 3 — Impossible Case

$ Input: stamp = "abc", target = "aabcb"

› Output: []

💡 Note: Cannot create target with given stamp - the 'aa' at start cannot be formed by 'abc'

Constraints

1 ≤ stamp.length ≤ target.length ≤ 1000
stamp and target consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Initial State

String s filled with '?' characters

Stamping Process

Place stamp at various positions to build target

Target Achieved

Return sequence of positions used

Key Takeaway

🎯 Key Insight: Work backwards from target by greedily removing stamp patterns to avoid exponential search

Asked in

G Google 15 f Facebook 8

The key insight is to work backwards from the target string by removing stamp effects. The greedy reverse approach starts with the target and greedily removes stamps that could have contributed to the current state. Best approach is greedy reverse stamping. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Reverse Stamping	O(n²)	O(n)	Work backwards from target by greedily removing stamps that made progress
Brute Force Forward Simulation	O(m^k)	O(k)	Try all possible stamping sequences by simulating forward from '?' to target

Greedy Reverse Stamping — Algorithm Steps

Step 1: Start with target string
Step 2: Find positions where stamp could have been placed
Step 3: Remove stamp effects greedily until reaching all '?' state
Step 4: Reverse the sequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Target

Begin with target string 'abcba'

Find Stamp

Identify where 'abc' stamp was placed

Remove Effect

Replace stamp area with '?'

Code -

solution.c — C

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

#define MAX_LEN 1000
#define MAX_MOVES 10000

int hasStarOrMatch(char* target, int pos, char* stamp, int stampLen) {
    int hasStar = 0;
    for (int i = 0; i < stampLen; i++) {
        if (target[pos + i] == '?') {
            hasStar = 1;
        } else if (target[pos + i] != stamp[i]) {
            return 0;
        }
    }
    return hasStar;
}

int* solution(char* stamp, char* target, int* returnSize) {
    int n = strlen(target);
    int m = strlen(stamp);
    int* result = (int*)malloc(MAX_MOVES * sizeof(int));
    int resultSize = 0;
    int stars = 0;
    char targetCopy[MAX_LEN];
    strcpy(targetCopy, target);
    
    while (stars < n) {
        int found = 0;
        for (int i = 0; i <= n - m; i++) {
            if (hasStarOrMatch(targetCopy, i, stamp, m)) {
                found = 1;
                result[resultSize++] = i;
                for (int j = 0; j < m; j++) {
                    if (targetCopy[i + j] != '?') {
                        stars++;
                    }
                    targetCopy[i + j] = '?';
                }
                break;
            }
        }
        
        if (!found || resultSize > 10 * n) {
            *returnSize = 0;
            free(result);
            return NULL;
        }
    }
    
    // Reverse result
    for (int i = 0; i < resultSize / 2; i++) {
        int temp = result[i];
        result[i] = result[resultSize - 1 - i];
        result[resultSize - 1 - i] = temp;
    }
    
    *returnSize = resultSize;
    return result;
}

int main() {
    char stamp[MAX_LEN], target[MAX_LEN];
    fgets(stamp, sizeof(stamp), stdin);
    stamp[strcspn(stamp, "\n")] = 0;
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    int returnSize;
    int* result = solution(stamp, target, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    if (result) free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs at most n times, inner loop checks n positions each time

⚠ Quadratic Growth

Space Complexity

O(n)

Store the result array and temporary string state

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

450 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

Greedy Reverse Stamping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler