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

1. Build a set of characters present in source.
2. For each character in target, check if it exists in source. If any character is missing, return -1.
3. Start with concatenatedSource = source and count = 1.
4. While target is not a subsequence of concatenatedSource:
   • Append source to concatenatedSource.
   • Increment count.
5. 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 count

Time & Space Complexity

• Time complexity: $O(T^2 \cdot S)$
• Space complexity: $O(TS)$

where $S$ is the length of source and $T$ is the length of target

---

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

1. Create a set of characters in source. Return -1 if any character in target is missing.
2. Initialize sourceIterator = 0 and count = 0.
3. For each character in target:
   • If sourceIterator == 0, we are starting a new pass through source, so increment count.
   • While source[sourceIterator] does not match the current character:
     • Move sourceIterator forward using modulo.
     • If sourceIterator wraps to 0, increment count.
   • After finding the match, advance sourceIterator by one (with modulo).
4. 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 count

Time & Space Complexity

• Time complexity: $O(S \cdot T)$
• Space complexity: $O(1)$ constant space used

where $S$ is the length of source and $T$ is the length of target

---

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

1. Build an inverted index: for each character, store a sorted list of its positions in source.
2. Initialize sourceIterator = 0 and count = 1.
3. 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 count and use the first occurrence.
   • Update sourceIterator to be one past the found index.
4. Return count.

Time & Space Complexity

• Time complexity: $O(S + T \log(S))$
• Space complexity: $O(S)$

where $S$ is the length of source and $T$ is the length of target

---

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

1. Create a 2D array nextOccurrence of size source.length x 26.
2. Initialize the last row: set all entries to -1, then set the entry for the last character of source to source.length - 1.
3. Fill the array from right to left:
   • Copy values from nextOccurrence[i+1] to nextOccurrence[i].
   • Update nextOccurrence[i][source[i]] to i.
4. Initialize sourceIterator = 0 and count = 1.
5. For each character in target:
   • If nextOccurrence[0][c] == -1, the character does not exist in source; return -1.
   • If sourceIterator == source.length or nextOccurrence[sourceIterator][c] == -1, increment count and reset sourceIterator = 0.
   • Set sourceIterator = nextOccurrence[sourceIterator][c] + 1.
6. 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 count

Time & Space Complexity

• Time complexity: $O(S + T)$
• Space complexity: $O(S)$

where $S$ is the length of source and $T$ is the length of target

---

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.