Shortest Way to Form String - Practice Coding Problems

Shortest Way to Form String - Problem

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not.

Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.

Input & Output

Example 1 — Basic Case

$ Input: source = "abc", target = "abcbc"

› Output: 2

💡 Note: First subsequence: "abc" matches "abc". Second subsequence: "bc" matches remaining "bc". Total: 2 subsequences needed.

Example 2 — Single Character

$ Input: source = "abc", target = "aaa"

› Output: -1

💡 Note: Source only has one 'a' at position 0, but target needs three 'a's. Since 'a' appears only once in source, it's impossible to form target.

Example 3 — Perfect Match

$ Input: source = "xyz", target = "xz"

› Output: 1

💡 Note: Target "xz" can be formed as a single subsequence from source "xyz" by taking characters at positions 0 and 2.

Constraints

1 ≤ source.length, target.length ≤ 1000
source and target consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Source string and target string to be formed

Process

Greedily match characters using subsequences

Output

Minimum number of subsequences needed

Key Takeaway

🎯 Key Insight: Greedily match as many characters as possible in each pass through source to minimize subsequence count

Asked in

G Google 12 a Amazon 8 f Facebook 6 M Microsoft 4

The key insight is to greedily match as many characters as possible in each pass through the source string. We first check if all target characters exist in source (return -1 if not), then repeatedly scan source to match target characters in order. The two pointers approach is most practical with O(n×m) time and O(1) space, while binary search optimization achieves O(n + m log n) time with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(n + m log n)	O(n)	Pre-index character positions and use binary search for faster character lookup
Two Pointers Greedy	O(n × m)	O(1)	Use two pointers to greedily match characters from source to target
Brute Force	O(2^n × m)	O(2^n)	Try all possible ways to form subsequences from source

Binary Search Optimization — Algorithm Steps

Build index of character positions for source
For each target character, binary search for next position
Reset position when no valid next position found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Index

Create position arrays for each character

Binary Search

Find next occurrence after current position

Update Position

Move to found position or reset for new subsequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_CHARS 256
#define MAX_LEN 1000

struct CharPos {
    int positions[MAX_LEN];
    int count;
};

int binarySearch(int* arr, int size, int target) {
    int left = 0, right = size;
    while (left < right) {
        int mid = (left + right) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int solution(const char* source, const char* target) {
    struct CharPos charPositions[MAX_CHARS];
    memset(charPositions, 0, sizeof(charPositions));
    
    // Build index of character positions
    for (int i = 0; source[i]; i++) {
        unsigned char c = (unsigned char)source[i];
        charPositions[c].positions[charPositions[c].count++] = i;
    }
    
    // Check if all target characters exist
    for (int i = 0; target[i]; i++) {
        unsigned char c = (unsigned char)target[i];
        if (charPositions[c].count == 0) {
            return -1;
        }
    }
    
    int count = 0;
    int currentPos = -1;
    
    for (int i = 0; target[i]; i++) {
        unsigned char c = (unsigned char)target[i];
        struct CharPos* pos = &charPositions[c];
        
        // Binary search for next position after currentPos
        int idx = binarySearch(pos->positions, pos->count, currentPos);
        
        if (idx >= pos->count) {
            // Need to start new subsequence
            count++;
            currentPos = pos->positions[0];
        } else {
            // Continue current subsequence
            if (currentPos == -1) {
                count++;
            }
            currentPos = pos->positions[idx];
        }
    }
    
    return count;
}

int main() {
    char source[1001], target[1001];
    fgets(source, sizeof(source), stdin);
    fgets(target, sizeof(target), stdin);
    
    // Remove newlines
    source[strcspn(source, "\n")] = 0;
    target[strcspn(target, "\n")] = 0;
    
    int result = solution(source, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m log n)

Preprocessing takes O(n), each target character lookup takes O(log n)

⚡ Linearithmic

Space Complexity

O(n)

Store positions of each character in hash map with arrays

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler