class Solution:
def shortestWay(self, source: str, target: str) -> int:
# Preprocess: build a mapping from char to all positions in source
from collections import defaultdict
pos = defaultdict(list)
for idx, ch in enumerate(source):
pos[ch].append(idx)
res = 1
i = 0 # pointer in target
n = len(target)
m = len(source)
src_idx = 0 # pointer in source
while i < n:
ch = target[i]
if ch not in pos:
return -1
# Binary search for first position >= src_idx
import bisect
idx_list = pos[ch]
k = bisect.bisect_left(idx_list, src_idx)
if k == len(idx_list):
# Need to start a new subsequence
res += 1
src_idx = 0
else:
src_idx = idx_list[k] + 1
i += 1
return res
class Solution {
public:
int shortestWay(string source, string target) {
// Preprocess: map char to all indices
unordered_map<char, vector<int>> pos;
for (int i = 0; i < source.size(); ++i)
pos[source[i]].push_back(i);
int res = 1, i = 0, src_idx = 0;
while (i < target.size()) {
char ch = target[i];
if (!pos.count(ch))
return -1;
auto& idxs = pos[ch];
auto it = lower_bound(idxs.begin(), idxs.end(), src_idx);
if (it == idxs.end()) {
res++;
src_idx = 0;
} else {
src_idx = *it + 1;
i++;
}
}
return res;
}
};
class Solution {
public int shortestWay(String source, String target) {
Map<Character, List<Integer>> pos = new HashMap<>();
for (int i = 0; i < source.length(); ++i) {
pos.computeIfAbsent(source.charAt(i), k -> new ArrayList<>()).add(i);
}
int res = 1, i = 0, srcIdx = 0;
while (i < target.length()) {
char ch = target.charAt(i);
if (!pos.containsKey(ch)) return -1;
List<Integer> idxs = pos.get(ch);
int k = Collections.binarySearch(idxs, srcIdx);
if (k < 0) k = -k - 1;
if (k == idxs.size()) {
res++;
srcIdx = 0;
} else {
srcIdx = idxs.get(k) + 1;
i++;
}
}
return res;
}
}
var shortestWay = function(source, target) {
// Preprocess: map char to all indices in source
let pos = {};
for (let i = 0; i < source.length; ++i) {
if (!pos[source[i]]) pos[source[i]] = [];
pos[source[i]].push(i);
}
let res = 1, i = 0, srcIdx = 0;
while (i < target.length) {
let ch = target[i];
if (!pos[ch]) return -1;
let idxs = pos[ch];
// Binary search for first index >= srcIdx
let l = 0, r = idxs.length;
while (l < r) {
let mid = (l + r) >> 1;
if (idxs[mid] < srcIdx) l = mid + 1;
else r = mid;
}
if (l == idxs.length) {
res++;
srcIdx = 0;
} else {
srcIdx = idxs[l] + 1;
i++;
}
}
return res;
};
source and target. You are allowed to form the target string by repeatedly choosing subsequences from source and concatenating them together. A subsequence is formed by deleting some (possibly zero) characters from source without changing the order of the remaining characters. Your task is to find the minimum number of times you must take a subsequence from source (possibly reusing source multiple times) so that their concatenation equals target. If it is impossible to form target from source, return -1.source (cannot rearrange characters).source as many times as needed, but you must always start from the beginning after each use.target does not appear in source, return -1.target to source one by one, possibly restarting source whenever you reach the end or can't find a match. However, a brute-force approach of trying all possible subsequences would be far too slow.target left-to-right, greedily matching as many characters as possible in a single pass through source. Each time you can no longer match the next character (either because you reached the end of source or the character doesn't appear later), you restart from the beginning of source and keep going. To do this efficiently, you need a way to quickly find the next occurrence of each character in source after a certain index (this is where preprocessing and binary search come in).
source, record all the indices where it appears. This lets you quickly find where a character occurs in source using a hash map or array.target: Use two pointers: one for target and one for source. For each character in target, use binary search to find the next occurrence of that character in source at or after the current source pointer.source pointer to just after the matched character, and move to the next target character).source), increment your answer (number of subsequences), and restart the source pointer from the beginning.target doesn't exist in source at all, return -1 immediately.target. The total number of restarts plus the initial pass gives you the minimum number of subsequences needed.
By using a mapping from character to indices and binary search, you avoid scanning source repeatedly, making the solution efficient even for large strings.
source = "abc", target = "abcbc"source:
'a' (source[0]), move to next character in both.'b' (source[1]), move to next character in both.'c' (source[2]), move to next character in both. Now, source is exhausted.source (second subsequence):
'b'. Find 'b' at source[1], move both pointers.'c'. Find 'c' at source[2], move both pointers.target has been matched using 2 subsequences of source.
If target had a character not in source (e.g. 'd'), we would return -1.
n + m * log n), where n is the length of source, and m is the length of target. Each character in target may require a binary search over the positions in source.
n), for storing the positions of each character in source.
This makes the solution efficient and practical for large inputs.
target greedily, always matching as many characters as possible in a single pass through source. By preprocessing source into a mapping of character positions and using binary search, we avoid unnecessary repeated scans and achieve optimal performance. This approach balances clarity and efficiency, making it an elegant solution to the problem.