Stamping The Sequence

Link

Description

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?", 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 * 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.

Example 1:

• 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.

Example 2:

• 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 <= stamp.length <= target.length <= 1000
• stamp and target consist of lowercase English letters.

Solution

Topological Sorting

See reference (Chinese).

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        int m = stamp.size(), n = target.size();
        vector<int> inDegree(n - m + 1, m);
        vector<vector<int>> edges(n);
        queue<int> q;

        for (int i = 0; i < n - m + 1; i++) {
            for (int j = 0; j < m; j++) {
                if (target[i + j] == stamp[j]) {
                    if (--inDegree[i] == 0)
                        q.push(i);
                } else {
                    edges[i + j].push_back(i);
                }
            }
        }

        vector<bool> seen(n, false);
        vector<int> res;
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            res.push_back(current);

            for (int i = 0; i < m; i++) {
                if (!seen[current + i]) {
                    seen[current + i] = true;
                    for (auto&& edge : edges[current + i]) {
                        if (--inDegree[edge] == 0)
                            q.push(edge);
                    }
                }
            }
        }

        if (res.size() < n - m + 1)
            return {};
        reverse(res.begin(), res.end());
        return res;
    }
};

Greedy Solution (Easier to Understand)

class Solution {
private:
    // Attempts to stamp the target starting at position k
    // Returns true if a stamping operation was successful, false otherwise
    bool tryStamp(string& stamp, string& target, int start) {
        // Indicates if any character was successfully stamped
        bool isStamped = false;
        int stampLen = stamp.size();

        // Check if the segment from start with length of stamp can be stamped
        for (int i = 0; i < stampLen; i++) {
            if (target[start + i] == '?') continue;  // Skip already stamped characters
            if (target[start + i] != stamp[i]) return false;  // Mismatch found, cannot stamp here
            isStamped = true;  // At least one character matches and can be stamped
        }

        // If stamping is possible, replace the corresponding segment in target with '?'
        if (isStamped) {
            fill(target.begin() + start, target.begin() + start + stampLen, '?');
            return true;
        }
        return false;  // No stamping was possible
    }

public:
    vector<int> movesToStamp(string stamp, string target) {
        vector<int> res;  // Stores the sequence of stamp operations
        bool stamped = true;  // Flag to check if any stamping happened in a round

        while (stamped) {
            stamped = false;  // Reset flag for the current round

            // Try stamping at every possible starting position
            for (int i = 0; i <= target.size() - stamp.size(); i++) {
                if (tryStamp(stamp, target, i)) {
                    res.push_back(i);  // Record successful stamp position
                    stamped = true;  // Indicate that a stamping happened
                }
            }
        }

        // If the entire target is stamped, return the reversed result sequence
        if (target == string(target.size(), '?')) {
            reverse(res.begin(), res.end());
            return res;
        }
        // If not all characters could be stamped, return an empty result
        return {};
    }
};

Time Complexity:

1. Outer Loop (While Loop): This loop runs until no more stamping operations can be performed. In the worst case, this could potentially run \(O(n - m + 1)\) times, where \(n\) is the length of the target string and \(m\) is the length of the stamp string. However, this worst-case scenario is highly unlikely because each successful stamp operation should progressively reduce the number of potential stamping locations. A more realistic upper bound involves considering the number of '?' characters introduced per iteration, but exact analysis can be complex due to the greedy nature of the algorithm. For analysis purposes, let's denote the number of iterations in this loop as \(I\).

2. Inner Loop (For Loop): The inner loop iterates over every possible starting position for the stamp in the target string, which is \(O(n - m + 1)\).

3. Stamping Check and Operation (tryStamp Function): Within this loop, for each position, the stamping operation (including both the check and the actual stamping) takes \(O(m)\) time, where \(m\) is the length of the stamp string.

Combining these, the total time complexity can be approximated as \(O(I \times (n - m + 1) \times m)\). The value of \(I\) depends on the specifics of the input but is bounded by the length of the target string \(n\) in the worst case, leading to a rough upper bound of \(O(n^2 \cdot m)\) when considering highly inefficient stamp placements. However, in practical scenarios, especially with more random or favorable input patterns, \(I\) will be much smaller, and the algorithm will perform significantly better than this worst-case analysis suggests.

Space Complexity:

1. Result Vector (result): The space taken by the result vector depends on the number of stamping operations performed, which is at most \(O(n - m + 1)\) in the worst case, as you can't stamp more times than there are positions in the target string for the stamp to fit.

2. Temporary Storage: The function uses a constant amount of extra space for variables and does not allocate variable-size data structures proportional to the input size, except for the modifications directly made to the input target string, which does not count towards additional space complexity since it is an in-place operation.