source: https://leetcode.com/problems/shortest-way-to-form-string/description/
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.
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:
- 1 <= source.length, target.length <= 1000
- source and target consist of lowercase English letters.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
class Solution { public int shortestWay(String source, String target) { Map<Character, List<Integer>> map = new HashMap<>(); for(int i=0;i<source.length();i++){ char s = source.charAt(i); map.computeIfAbsent(s, k->new ArrayList<>()).add(i); } int t = target.length(); int j=-1; int count = 1; for(int i=0;i<t;i++){ char tc = target.charAt(i); if(map.containsKey(tc)){ int idx = findNextIndex(map.get(tc), j+1); //if idx == -1 then reset j to zero if(idx==-1){ count++; j = idx; //find the index greater than or equal to 0 idx = findNextIndex(map.get(tc), j+1); } j = idx; }else{ //character is not in source string return -1; } } return count; } //find the index that is greater than or equal to the value idx //binary search private int findNextIndex(List<Integer> l, int idx){ int lo = 0; int hi = l.size()-1; while(lo<hi){ int mid = (lo+hi)/2; int x = l.get(mid); if(x >= idx){ hi = mid; }else { lo = mid+1; } } return l.get(lo)>=idx?l.get(lo):-1; } } |
Time Complexity: O(S + TlogS)
- O(S) -> to create a map to store indices
- O(TlogS) -> for each character in Target T we need to binary search the index of that character in Source S
Space Complexity: O(S)
- O(S) -> to store indices of characters in Source