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 = ?????$ 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?$, or
• 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 \times 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 \times target.length$ turns, return an empty array.

Example

Input: stamp = "abc", target = "ababc"
Output: [0,2]
Explanation: Initially s = "?????".
- Place stamp at index 0 to get "abc??".
- Place stamp at index 2 to get "ababc".
[1,0,2] would also be accepted as an answer, as well as some other answers.

Input: stamp = "abca", target = "aabcaca"
Output: [3,0,1]
Explanation: Initially s = "???????".
- Place stamp at index 3 to get "???abca".
- Place stamp at index 0 to get "abcabca".
- Place stamp at index 1 to get "aabcaca".

Constraints

• $1 \leq stamp.length \leq target.length \leq 1000$
• $stamp$ and $target$ consist of lowercase English letters

Submit your solution at here

Solution

Intuition

We use greedy approach to do the stamping. We will do it in multiple rounds.

• At round 0, we find all “full match” candidates to stamp. It’s seems the best we can do at this point
• At round 1, for every stamp $x$ we made in round 0, we go to the left and right, then greedily find the longest possible stamp right next to $x$, stamp them under the stamps made in round 0
• At round 2, for every stamp $y$ we made in round 1, we again go to the left and right, find the longest possible stamp to make, stamp them under the stamps made in previous rounds
• The loop ends when we run out of moves or when we can’t find a stamp anymore
• I can’t prove that this method will yield minimum number of steps. And it seems that indeed it doesn’t. If there is a test case where the optimal answer is exactly $n \times 10$ this method would very likely fail. I tried and luckily it passed all the test cases

Approach

We maintain 2 queues ql, qr to keep track of which item need to check on the left and on the right. Each time we do a stamp, we put them into queue, so we can revise them in the next round. After finishing the loop. Reverse the result and we get the answer.

Complexity

• Time complexity: Running time is $T((n-m+1) \times m)$ where $n$ is target length and $m$ is stamp length, in worst case where $m = n \div 2$ we will have $O(n^2)$

• Space complexity: $O(n)$

Code

class Solution {
public:
    bool canStamp(string& target, string& paper, string& stamp, int k) {
        if(k < 0) {
            return false;
        }
        int i = 0;
        int m = stamp.size();
        bool matched = false;
        for(int i = 0;i<m;i++) {
            if(paper[i+k] != '?') {
                continue;
            }
            matched = true;
            if(target[i+k] != stamp[i]) {
                return false;
            }
        }
        return matched;
    }

    void stampUnder(string& paper, string& stamp, int k) {
        //cout<<"stamp at "<<k<<" paper = "<<paper<<endl;
        int i = 0;
        int m = stamp.size();
        for(int i = 0;i<m;i++) {
            if(paper[i+k] != '?') {
                continue;
            }
            paper[i+k] = stamp[i];
        }
    }
    vector<int> movesToStamp(string stamp, string target) {
        int m = stamp.size();
        int n = target.size();
        int move = 0;
        int moveMax = 10*n;
        string paper(n, '?');
        vector<int> ret;
        queue<int> ql;
        queue<int> qr;
        for(int i = 0;i<=n-m;i++) {
            if(!canStamp(target, paper, stamp, i)) {
                continue;
            }
            ql.push(i);
            qr.push(i);
            stampUnder(paper, stamp, i);
            ret.push_back(i);
            i += m-1;
            move++;
        }
        while(!(ql.empty() && qr.empty()) && move <= moveMax) {
            int x = ql.size();
            while(x--) {
                auto k = ql.front();
                ql.pop();
                int k0 = k - m + 1;
                for(int i = k0;i<k;i++) {
                    if(!canStamp(target, paper, stamp, i)) {
                        continue;
                    }
                    ql.push(i);
                    move++;
                    stampUnder(paper, stamp, i);
                    ret.push_back(i);
                    break;
                }
            }
            x = qr.size();
            while(x--) {
                auto k = qr.front();
                qr.pop();
                int kn = min(k + m - 1, n-m);
                for(int i = kn;i>k;i--) {
                    if(!canStamp(target, paper, stamp, i)) {
                        continue;
                    }
                    qr.push(i);
                    move++;
                    stampUnder(paper, stamp, i);
                    ret.push_back(i);
                    break;
                }
            }
        }
        if(move > moveMax) {
            ret.clear();
        } else {
            for(auto c: paper) {
                if(c == '?') {
                    ret.clear();
                    break;
                }
            }
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};