Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1055.html
1055. Shortest Way to Form String
Level
Medium
Description
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
.
Solution
Use two pointers in source
and target
respectively. Both pointers are initialized to 0.
Each time starting from the pointer of target
, find the longest subsequence of source
in target
. A subsequence in target
ends when either the pointer in source
reaches the end or the pointer in target
reaches the end. If a longest subsequence has length 0, then the character in target
does not exist in source
, so return 1. Otherwise, increase the number of subsequences by 1, and find the next subsequence in target
starting from the updated pointer in target
. Finally, return the number of subsequences.

class Solution { public int shortestWay(String source, String target) { int count = 0; int targetLength = target.length(); int startIndex = 0; while (startIndex < targetLength) { startIndex = longestSubsequence(source, target, startIndex); if (startIndex < 0) return 1; else count++; } return count; } public int longestSubsequence(String source, String target, int startIndex) { int sourceLength = source.length(), targetLength = target.length(); int sourceIndex = 0, targetIndex = startIndex; while (sourceIndex < sourceLength && targetIndex < targetLength) { char c1 = source.charAt(sourceIndex), c2 = target.charAt(targetIndex); if (c1 == c2) targetIndex++; sourceIndex++; } if (targetIndex == startIndex) return 1; else return targetIndex; } }

class Solution: def shortestWay(self, source: str, target: str) > int: def f(i, j): while i < m and j < n: if source[i] == target[j]: j += 1 i += 1 return j m, n = len(source), len(target) ans = j = 0 while j < n: k = f(0, j) if k == j: return 1 j = k ans += 1 return ans

class Solution { public: int shortestWay(string source, string target) { int m = source.size(), n = target.size(); int ans = 0, j = 0; while (j < n) { int i = 0; bool ok = false; while (i < m && j < n) { if (source[i] == target[j]) { ok = true; ++j; } ++i; } if (!ok) { return 1; } ++ans; } return ans; } };

func shortestWay(source string, target string) int { m, n := len(source), len(target) ans, j := 0, 0 for j < n { ok := false for i := 0; i < m && j < n; i++ { if source[i] == target[j] { ok = true j++ } } if !ok { return 1 } ans++ } return ans }