LeetCode 936: Stamping The Sequence Solution

Master LeetCode problem 936 (Stamping The Sequence), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

936. Stamping The Sequence

Hard

String Stack Greedy Queue

Problem Explanation

Explanation:

To solve this problem, we can use a greedy algorithm approach. We will repeatedly try to stamp the target string with the stamp, and each time we successfully stamp part of the target, we update the target string and record the index of the left-most letter being stamped.

Initially, we create a set to store all the indices where we can stamp the target with the stamp.
We repeat the following steps until the target becomes all stamped or we reach the maximum allowed turns:
- Iterate over the target string and check if the stamp can be placed starting at each index.
- If the stamp can be placed at a particular index, update the target string by stamping the characters and add the index to the set of stamped indices.
If the target becomes all stamped, return the stamped indices in reverse order (as we are stamping from the end to the beginning). Otherwise, return an empty array.

Solution Code

class Solution {
    public int[] movesToStamp(String stamp, String target) {
        char[] s = target.toCharArray();
        char[] t = stamp.toCharArray();
        int S = s.length, T = t.length;
        List<Integer> stamped = new ArrayList<>();
        boolean[] visited = new boolean[S];
        boolean changed = true;
        
        while (changed) {
            changed = false;
            for (int i = 0; i <= S - T; i++) {
                boolean match = false;
                for (int j = 0; j < T; j++) {
                    if (s[i + j] == t[j] || s[i + j] == '?') {
                        match = true;
                    } else {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    changed = true;
                    for (int j = 0; j < T; j++) {
                        if (s[i + j] != '?') {
                            s[i + j] = '?';
                            stamped.add(i + j);
                        }
                    }
                    for (int k = 0; k < S; k++) {
                        visited[k] = visited[k] || i <= k && k < i + T;
                    }
                }
            }
        }
        
        for (int i = 0; i < S; i++) {
            if (!visited[i] && s[i] != '?') return new int[0];
        }
        
        int[] result = new int[stamped.size()];
        for (int i = 0; i < stamped.size(); i++) {
            result[i] = stamped.get(stamped.size() - 1 - i);
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 936 (Stamping The Sequence)?

This page provides optimized solutions for LeetCode problem 936 (Stamping The Sequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 936 (Stamping The Sequence)?

The time complexity for LeetCode 936 (Stamping The Sequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 936 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 936 in Java, C++, or Python.

Back to LeetCode Solutions