We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Way to Form String

Number: 1051

Difficulty: Medium

Paid? Yes

Companies: Pinterest, Meta, Google

Problem Description

Given two strings source and target, the goal is to form target by concatenating the minimum number of subsequences taken from source. A subsequence is defined as a string that can be derived from another string by deleting some or no elements without changing the order of the remaining characters. If it is not possible to form target using subsequences of source, return -1.

Key Insights

  • Check if every character in target exists in source; if not, the answer is -1.
  • Use a greedy two-pointer strategy: iterate over target while scanning source for matching characters.
  • During each pass over source, match as many characters as possible from target.
  • Count the number of passes (subsequences) required until the target is completely matched.
  • An optimized approach may precompute indices for binary search; however, the basic greedy simulation is efficient for the given constraints.

Space and Time Complexity

Time Complexity: O(n * m) in the worst-case, where n = length of source and m = length of target.
Space Complexity: O(1) for the greedy simulation (O(n) if additional data structures for binary search are used).

Solution

The solution uses a greedy two-pointer approach. We simulate the process of reading the target by repeatedly scanning through the source string. Each scan through source is treated as one subsequence concatenated to form the target. A pointer in the target moves forward whenever a matching character is found in source. If a complete pass through source does not advance the target pointer, then it is impossible to form the target and we return -1. The algorithm counts the number of passes required until the target is fully matched.

Code Solutions

# Python solution using greedy two-pointer approach

def shortestWay(source, target):
    count = 0  # Count of subsequences used
    t_index = 0
    t_len = len(target)
    
    # Pre-check: if any character in target is not in source, return -1
    if set(target) - set(source):
        return -1

    # While there are still characters in target to match
    while t_index < t_len:
        s_index = 0  # Pointer for source
        progress = False  # Flag to check if we made progress this pass
        
        # Iterate through source and try to match target characters
        while s_index < len(source) and t_index < t_len:
            if source[s_index] == target[t_index]:
                t_index += 1  # Move to next character in target
                progress = True
            s_index += 1
        
        count += 1  # One subsequence used for this pass
        
        # If no progress was made, then it is impossible to form the target
        if not progress:
            return -1

    return count

# Example usage:
# print(shortestWay("abc", "abcbc"))  # Output: 2
← Back to All Questions