[LeetCode] Shortest Way to Form String

1055. Shortest Way to Form String

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).

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

  • Time : O(nlogn)
  • Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int shortestWay(string source, string target) {
unordered_map<char, set<int>> seq;
for(int i = 0; i < source.length(); i++) {
seq[source[i]].insert(i);
}
int res = 0, mi = -1;
for(auto& t : target) {
if(!seq.count(t)) return -1; //not contain character case

auto it = seq[t].upper_bound(mi);
if(it == seq[t].end()) {
res++;
mi = *seq[t].begin();
} else mi = *it;
}

return res + (mi >= 0);
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/02/18/PS/LeetCode/shortest-way-to-form-string/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.