You are given a string S. You can use your mouse only once to place the mouse pointer on any position in the string and use the Backspace key on your keyboard. You have to determine if a string X can be obtained by performing such an operation. If it is possible, print the string that will be removed by using Backspace. Else, print -1. Note: You are allowed to press the Backspace key multiple times but not allowed to use the mouse more than one time. Function Description Complete the function getStringToRemove in the editor. getStringToRemove has the following parameters:

• 1. String S: the original string
• 2. String X: the target string to obtain Returns String: the string of characters that need to be removed to obtain the string X from S, if possible; otherwise, "-1"

Constraints

X.length ≤ S.length

Example 1

Input:

S = "InterviewMocha"
X = "IMocha"

Output:

"nterview"

Explanation: Placing the mouse pointer at w, and pressing the Backspace key 8 times, will convert the string InterviewMocha into the string IMocha. So, the string of characters that need to be removed to obtain the string X from S is nterview. Hence, the output is nterview.

解法

由于鼠标只能放一次然后按多次 Backspace，被删的一定是 S 中某段连续子串，且删除位置必须使 X = S[:i] + S[i+k:](i 为前缀长度，k 为删除长度)。前缀长度 i ∈ [0, len(X)]，要求 S 前 i 个字符与 X 前 i 个相同、且 S 后 len(X) - i 个字符与 X 后 len(X) - i 个相同。从大到小枚举 i，找到第一个合法位置即输出被删的子串。复杂度 O(|S|)，空间 O(|S|)。

def get_string_to_remove(S: str, X: str) -> str:
    n, m = len(S), len(X)
    if m > n:
        return "-1"
    for i in range(m, -1, -1):
        if S[:i] == X[:i] and S[n - (m - i):] == X[i:]:
            removed = S[i: n - (m - i)]
            if removed:
                return removed
    return "-1"

class Solution {
    String getStringToRemove(String S, String X) {
        int n = S.length(), m = X.length();
        if (m > n) return "-1";
        for (int i = m; i >= 0; i--) {
            if (S.substring(0, i).equals(X.substring(0, i))
                && S.substring(n - (m - i)).equals(X.substring(i))) {
                String removed = S.substring(i, n - (m - i));
                if (!removed.isEmpty()) return removed;
            }
        }
        return "-1";
    }
}

class Solution {
public:
    string getStringToRemove(string S, string X) {
        int n = S.size(), m = X.size();
        if (m > n) return "-1";
        for (int i = m; i >= 0; --i) {
            if (S.substr(0, i) == X.substr(0, i)
                && S.substr(n - (m - i)) == X.substr(i)) {
                string removed = S.substr(i, n - (m - i) - i);
                if (!removed.empty()) return removed;
            }
        }
        return "-1";
    }
};