Shortest Way To Form String - Leetcode Solution

Problem

Given two strings 'source' and 'target', return the minimum number of subsequences of 'source' that can be concatenated to form the 'target'. If it is impossible to form 'target' using the given 'source', return -1.

A subsequence of a string is a new string generated by deleting some characters of the original string without changing the relative order of the remaining characters.

Example

Input: source = "abc", target = "abcbc" Output: 2 Explanation: The target "abcbc" can be formed by "abc" and "bc", which are subsequences of "abc".

Input: source = "abc", target = "acdbc" Output: -1 Explanation: The target string cannot be formed by the subsequences of "abc".

Solution

The problem can be solved using a two-pointer approach. Generate subsequences of 'source' until it reaches a point where it can generate the 'target' string.

Algorithm

1. In the first step, we will check if all characters of the target are present in the source string. If not, return -1.
2. Initialize two pointers: 'i' to traverse 'source' and 'j' to traverse 'target'.
3. Iterate until 'j' reaches the end of 'target'.
4. If the characters at 'i' and 'j' are equal, increment both pointers.
5. Otherwise, increment 'i' until the character at i is equal to the character at j.
6. If we complete iterating through the 'source' without building the complete 'target', increment the number of subsequence we have built and start again.

Code

def shortestWay(source, target): i, j, count = 0, 0, 0 while j < len(target): if target[j] not in source: return -1 if source[i] == target[j]: j += 1 i += 1 if i == len(source): i = 0 count += 1 if i != 0: count += 1 return count

Complexity Analysis

Time Complexity: O(m * n), where m and n are the lengths of the source and target strings, respectively. The worst-case scenario occurs when all characters of the target need to be matched against all the characters of the source.

Space Complexity: O(1), as we are not using any extra space.

Summary

In this problem, we have learned how to find the minimum number of subsequences of the 'source' string that can be concatenated to form the 'target' string. We used a two-pointer approach to solve this problem, which makes it efficient in terms of time and space complexity.

1