From any string, we can form a subsequence of that string by deleting some number of characters (possibly no deletions).
Given two strings
source
and target
, return the minimum number of subsequences of source
such that their concatenation equals target
. If the task is impossible, return -1
.
Example 1:
Input: source = "abc", target = "abcbc" Output: 2 Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of source "abc".
Example 2:
Input: source = "abc", target = "acdbc" Output: -1 Explanation: The target string cannot be constructed from the subsequences of source string due to the character "d" in target string.
Example 3:
Input: source = "xyz", target = "xzyxz" Output: 3 Explanation: The target string can be constructed as follows "xz" + "y" + "xz".
Constraints:
- Both the
source
andtarget
strings consist of only lowercase English letters from "a"-"z". - The lengths of
source
andtarget
string are between1
and1000
.
(Some Bug with following input:
"ugxhfjvmzvkzzlmpryyiqxcujshflkreqqorcbefzvjsnfokfydgajitaqcsqlywizwvkjsqjqpjagvf"
"rfuexnetdlhtlniubuqmalbrmmxrzhmkrzcwswytnudndovcwbixttqrqnsglyhkmbwphztjottflnoj"
"rfuexnetdlhtlniubuqmalbrmmxrzhmkrzcwswytnudndovcwbixttqrqnsglyhkmbwphztjottflnoj"
class Solution {
public:
int shortestWay(string source, string target) {
multimap<char, int> mp;
for (int i = 0; i < source.size(); i++) {
char ch = source[i];
mp.insert({ch, i});
}
int ans = 0;
int prev_idx = -1;
multimap<char, int> tmp = mp;
for (auto ch : target) {
if (!mp.count(ch)) {
return -1;
}
multimap<char, int>::iterator it = tmp.find(ch);
if (it == tmp.end()) {
ans++;
tmp = mp;
it = tmp.find(ch);
prev_idx = it -> second;
} else {
int idx = it -> second;
if (prev_idx == -1 || idx < prev_idx) {
ans++;
}
prev_idx = idx;
}
tmp.erase(it);
}
return ans;
}
};
No comments:
Post a Comment