Shortest Way to Form String

Medium · Two Pointers · Explanation and code example

2D Array

How it works

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.

Steps

  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.

Complexity

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

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

Things to watch for

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.

Python code example

from collections import defaultdict

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

C++ code example

class Solution {
public:
    int shortestWay(string source, string target) {

        // Next Occurrence of Character after Index
        int nextOccurrence[source.length()][26];

        // Base Case
        for (int c = 0; c < 26; c++) {
            nextOccurrence[source.length() - 1][c] = -1;
        }
        nextOccurrence[source.length() - 1][source[source.length() - 1] - 'a'] = source.length() - 1;

        // Fill using recurrence relation
        for (int idx = source.length() - 2; idx >= 0; idx--) {
            for (int c = 0; c < 26; c++) {
                nextOccurrence[idx][c] = nextOccurrence[idx + 1][c];
            }
            nextOccurrence[idx][source[idx] - 'a'] = idx;
        }

        // Pointer to the current index in source
        int sourceIterator = 0;

        // Number of times we need to iterate through source
        int count = 1;

        // Find all characters of target in source
        for (char c : target) {

            // If the character is not present in source
            if (nextOccurrence[0][c - 'a'] == -1) {
                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 (sourceIterator == source.length() || nextOccurrence[sourceIterator][c - 'a'] == -1) {
                count++;
                sourceIterator = 0;
            }

            // Next occurrence of character in source after source_iterator
            sourceIterator = nextOccurrence[sourceIterator][c - 'a'] + 1;
        }

        // Return the number of times we need to iterate through source
        return count;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations