Prerequisites
Before attempting this problem, you should be comfortable with:
- Subsequence Concept - Understanding what makes one string a subsequence of another
- Two Pointers Technique - Using pointers to traverse and compare strings efficiently
- Binary Search - Finding elements in sorted arrays for optimized character lookups
- Precomputation / Dynamic Programming - Building lookup tables to enable O(1) queries for next character positions
1. Concatenate until Subsequence
Intuition
The most straightforward approach is to literally concatenate copies of source until target becomes a subsequence of the concatenated string. We first check if all characters in target exist in source; if not, it is impossible. Then we keep appending source to itself and check after each concatenation whether target is now a subsequence. The number of concatenations gives us our answer.
Algorithm
- Build a set of characters present in
source. - For each character in
target, check if it exists insource. If any character is missing, return-1. - Start with
concatenatedSource = sourceandcount = 1. - While
targetis not a subsequence ofconcatenatedSource:- Append
sourcetoconcatenatedSource. - Increment
count.
- Append
- Return
count.
class Solution:
def shortestWay(self, source: str, target: str) -> int:
# To check if to_check is subsequence of in_string
def is_subsequence(to_check, in_string):
i = j = 0
while i < len(to_check) and j < len(in_string):
if to_check[i] == in_string[j]:
i += 1
j += 1
return i == len(to_check)
# Set of all characters of the source. We could use a boolean array as well.
source_chars = set(source)
# Check if all characters of the target are present in the source
# If any character is not present, return -1
for char in target:
if char not in source_chars:
return -1
# Concatenate source until the target is a subsequence
# of the concatenated string
concatenated_source = source
count = 1
while not is_subsequence(target, concatenated_source):
concatenated_source += source
count += 1
# Number of concatenations done
return countTime & Space Complexity
- Time complexity:
- Space complexity:
where is the length of
sourceand is the length oftarget
2. Two Pointers
Intuition
Instead of building a huge concatenated string, we can simulate the process more efficiently. We iterate through target character by character, and for each character, we scan through source to find it. When we reach the end of source without fully matching target, we wrap around to the beginning of source and increment our count. Using modulo arithmetic, we can treat source as circular without actually concatenating it.
Algorithm
- Create a set of characters in
source. Return-1if any character intargetis missing. - Initialize
sourceIterator = 0andcount = 0. - For each character in
target:- If
sourceIterator == 0, we are starting a new pass throughsource, so incrementcount. - While
source[sourceIterator]does not match the current character:- Move
sourceIteratorforward using modulo. - If
sourceIteratorwraps to0, incrementcount.
- Move
- After finding the match, advance
sourceIteratorby one (with modulo).
- If
- Return
count.
class Solution:
def shortestWay(self, source: str, target: str) -> int:
# Set of all characters of source. Can use a boolean array too.
source_chars = set(source)
# Check if all characters of target are present in source
# If any character is not present, return -1
for char in target:
if char not in source_chars:
return -1
# Length of source to loop back to start of source using mod
m = len(source)
# Pointer for source
source_iterator = 0
# Number of times source is traversed. It will be incremented when
# while finding the occurrence of a character in target, source_iterator
# reaches the start of source again.
count = 0
# Find all characters of target in source
for char in target:
# If while finding, iterator reaches start of source again,
# increment count
if source_iterator == 0:
count += 1
# Find the first occurrence of char in source
while source[source_iterator] != char:
# Formula for incrementing while looping back to start.
source_iterator = (source_iterator + 1) % m
# If while finding, iterator reaches the start of source again,
# increment count
if source_iterator == 0:
count += 1
# Loop will break when char is found in source. Thus, increment.
# Don't increment count until it is not clear that target has
# remaining characters.
source_iterator = (source_iterator + 1) % m
# Return count
return countTime & Space Complexity
- Time complexity:
- Space complexity: constant space used
where is the length of
sourceand is the length oftarget
3. Inverted Index and Binary Search
Intuition
The two-pointer approach scans through source linearly for each character in target, which can be slow. We can speed this up by precomputing the positions of each character in source. For any character we need to find, we use binary search to quickly locate the next occurrence at or after our current position. If no such occurrence exists, we wrap to the beginning of source and start a new subsequence.
Algorithm
- Build an inverted index: for each character, store a sorted list of its positions in
source. - Initialize
sourceIterator = 0andcount = 1. - For each character in
target:- If the character does not exist in
source, return-1. - Binary search for the smallest index in the character's position list that is
>= sourceIterator. - If no such index exists (we have passed all occurrences), increment
countand use the first occurrence. - Update
sourceIteratorto be one past the found index.
- If the character does not exist in
- Return
count.
Time & Space Complexity
- Time complexity:
- Space complexity:
where is the length of
sourceand is the length oftarget
4. 2D Array
Intuition
We can achieve constant-time lookups by precomputing a 2D array where nextOccurrence[i][c] gives the index of the next occurrence of character c at or after position i in source. We build this array from right to left using dynamic programming: at each position, we copy the values from the next position and then update the current character's entry. This allows O(1) character lookups during the matching phase.
Algorithm
- Create a 2D array
nextOccurrenceof sizesource.length x 26. - Initialize the last row: set all entries to
-1, then set the entry for the last character ofsourcetosource.length - 1. - Fill the array from right to left:
- Copy values from
nextOccurrence[i+1]tonextOccurrence[i]. - Update
nextOccurrence[i][source[i]]toi.
- Copy values from
- Initialize
sourceIterator = 0andcount = 1. - For each character in
target:- If
nextOccurrence[0][c] == -1, the character does not exist insource; return-1. - If
sourceIterator == source.lengthornextOccurrence[sourceIterator][c] == -1, incrementcountand resetsourceIterator = 0. - Set
sourceIterator = nextOccurrence[sourceIterator][c] + 1.
- If
- Return
count.
class Solution:
def shortestWay(self, source: str, target: str) -> int:
# Length of source
source_length = len(source)
# Next Occurrence of Character after Index
next_occurrence = [defaultdict(int) for idx in range(source_length)]
# Base Case
next_occurrence[source_length -
1][source[source_length - 1]] = source_length - 1
# Using Recurrence Relation to fill next_occurrence
for idx in range(source_length - 2, -1, -1):
next_occurrence[idx] = next_occurrence[idx + 1].copy()
next_occurrence[idx][source[idx]] = idx
# Pointer for source
source_iterator = 0
# Number of times we need to iterate through source
count = 1
# Find all characters of target in source
for char in target:
# If character is not in source, return -1
if char not in next_occurrence[0]:
return -1
# If we have reached the end of source, or the character is not in
# source after source_iterator, loop back to beginning
if (source_iterator == source_length or
char not in next_occurrence[source_iterator]):
count += 1
source_iterator = 0
# Next occurrence of character in source after source_iterator
source_iterator = next_occurrence[source_iterator][char] + 1
# Return the number of times we need to iterate through source
return countTime & Space Complexity
- Time complexity:
- Space complexity:
where is the length of
sourceand is the length oftarget
Common Pitfalls
Forgetting to Check for Impossible Characters
Before attempting to form the target, you must verify that every character in target exists in source. If any character is missing, forming the target is impossible regardless of how many times you concatenate source. Skipping this check leads to infinite loops or incorrect results.
Off-by-One Errors When Wrapping Around Source
When using a pointer to track your position in source, a common mistake is mishandling the wrap-around logic. If you reach the end of source without finding the needed character, you must reset to the beginning and increment the count. Errors often occur when forgetting to increment the count upon wrap-around or when incorrectly resetting the pointer position.
Counting Subsequences Incorrectly
Another pitfall is miscounting the number of source copies needed. The count should increment each time you start a new pass through source, not each time you find a character. Starting with count = 0 instead of count = 1 or incrementing at the wrong point in the loop results in an off-by-one error in the final answer.