Minimum Number of Valid Strings to Form Target II

Minimum Number of Valid Strings to Form Target II - Problem

Array String Binary Search Dynamic Programming Segment Tree Rolling Hash String Matching Hash Function Hard

You are given an array of strings words and a string target.

A string x is called valid if x is a prefix of any string in words.

Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.

Input & Output

Example 1 — Multiple Valid Prefixes

$ Input: words = ["abc","ab","bc"], target = "abc"

› Output: 1

💡 Note: The target "abc" can be formed using just the single word "abc" which is a valid prefix of itself. This gives us the minimum count of 1.

Example 2 — Need Multiple Pieces

$ Input: words = ["ab","bc"], target = "abc"

› Output: 2

💡 Note: Target "abc" cannot be formed with a single word. We need "ab" + "bc" to get "abbc" which doesn't work, or "ab" + "c" but "c" is not available. Actually, we need "ab" to cover positions 0-1, then we need a valid prefix starting at position 2 to cover "c", but "bc" doesn't match "c". The answer would be -1 in this case.

Example 3 — Impossible Case

$ Input: words = ["ab","cd"], target = "ef"

› Output: -1

💡 Note: No word in the dictionary starts with 'e', so it's impossible to form target "ef" using any valid prefixes.

Constraints

1 ≤ words.length ≤ 100
1 ≤ words[i].length ≤ 26
1 ≤ target.length ≤ 5000
words[i] and target consist of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Dictionary words and target string

Find Prefixes

Identify which prefixes can match parts of target

Minimize Count

Find minimum number of prefixes needed

Key Takeaway

🎯 Key Insight: Use dynamic programming with efficient prefix matching to find the minimum number of dictionary prefixes needed to construct the target string.

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Meta 12

This problem requires finding the minimum number of valid prefixes to form a target string. The key insight is to use dynamic programming where dp[i] represents the minimum strings needed to form target[0:i]. The optimal approach combines DP with a Trie data structure for efficient prefix matching. Time: O(n·L + W·M), Space: O(W·M + n).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2^n)	O(n)	Try all possible ways to split target using valid prefixes recursively
DP with Trie Optimization	O(n·L + W·M)	O(W·M + n)	Use Trie data structure to efficiently find all valid prefix matches at each position
Dynamic Programming	O(n²m)	O(n)	Build up solution using 1D DP array to track minimum strings needed for each position

Recursive Backtracking — Algorithm Steps

Start from position 0 in target
Try each word as potential prefix match
If match found, recursively solve remaining substring
Return minimum count across all valid splits

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin at start of target string

Try Prefixes

Test each word as potential prefix match

Recurse

For valid matches, solve remaining substring

Code -

solution.c — C

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

#define MAX_WORDS 1000
#define MAX_LEN 1000

char words[MAX_WORDS][MAX_LEN];
char target[MAX_LEN];
int memo[MAX_LEN];
int word_count;
int target_len;

int dfs(int start) {
    if (start == target_len) {
        return 0;
    }
    if (memo[start] != -2) {
        return memo[start];
    }
    
    int min_count = INT_MAX;
    for (int i = 0; i < word_count; i++) {
        int word_len = strlen(words[i]);
        if (start + word_len <= target_len && strncmp(target + start, words[i], word_len) == 0) {
            int rest = dfs(start + word_len);
            if (rest != -1 && rest < min_count - 1) {
                min_count = 1 + rest;
            }
        }
    }
    
    memo[start] = (min_count == INT_MAX) ? -1 : min_count;
    return memo[start];
}

int solution() {
    for (int i = 0; i < target_len; i++) {
        memo[i] = -2;
    }
    return dfs(0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse words array
    word_count = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (end > token && (*end == ' ' || *end == '"' || *end == '\n')) {
            *end = '\0';
            end--;
        }
        strcpy(words[word_count], token);
        word_count++;
        token = strtok(NULL, ",]");
    }
    
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    target_len = strlen(target);
    
    int result = solution();
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Without memoization, each position has multiple recursive branches leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to length of target string

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

450 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

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler