Minimum Number of Valid Strings to Form Target I

Minimum Number of Valid Strings to Form Target I - Problem

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

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 — Basic Valid Formation

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

› Output: 2

💡 Note: We can form "abcab" using "abc" + "ab" = 2 valid strings, or "ab" + "c" + "ab" = 3 strings. The minimum is 2.

Example 2 — Impossible Formation

$ Input: words = ["abc","aaaa","bcdef"], target = "aabcdabc"

› Output: -1

💡 Note: Cannot form "aabcdabc" because no word has prefix "aa". The target cannot be formed with available prefixes.

Example 3 — Single Character Prefixes

$ Input: words = ["a","aa","aaa"], target = "aaaaaaa"

› Output: 3

💡 Note: Optimal way is "aaa" + "aaa" + "a" = 3 valid strings to form 7 characters total.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Dictionary words ["ab","abc","c"] and target "abcab"

Find Prefixes

Identify valid prefixes that can form parts of target

Optimize

Choose minimum combination: "abc" + "ab" = 2 strings

Key Takeaway

🎯 Key Insight: Use dynamic programming with trie structure to efficiently find minimum valid prefix combinations

Asked in

G Google 8 a Amazon 5 M Microsoft 4

The key insight is to use dynamic programming where each position represents the minimum valid strings needed to form the target up to that point. The optimal approach combines a trie data structure with DP for efficient prefix matching, achieving O(n×L) time complexity instead of O(n×m×k).

Common Approaches

Approach	Time	Space	Notes
✓ Trie + Dynamic Programming	O(n × L)	O(T + n)	Combine trie data structure with DP for efficient prefix matching
Dynamic Programming (Bottom-up)	O(n × m × k)	O(n)	Build solution incrementally using DP array to track minimum strings needed for each position
Brute Force with Recursion	O(n × m × k)	O(n)	Try all possible ways to split target using valid prefixes recursively

Trie + Dynamic Programming — Algorithm Steps

Build trie from all words in the dictionary
Initialize DP array with dp[0] = 0
For each position, traverse trie to find valid prefixes
Update DP values for positions reached by valid prefixes

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Trie

Construct trie from all words for fast prefix lookup

DP with Trie

At each position, traverse trie to find valid prefixes

Update DP

Update DP table when valid prefix endpoints are reached

Optimal Path

Trie eliminates redundant string comparisons

Code -

solution.c — C

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

#define MAX_LEN 1000
#define MAX_WORDS 100
#define ALPHABET_SIZE 26
#define INF 1000000

typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEnd;
} TrieNode;

TrieNode* createNode() {
    TrieNode* node = (TrieNode*)malloc(sizeof(TrieNode));
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    node->isEnd = 0;
    return node;
}

char words[MAX_WORDS][MAX_LEN];
int wordCount = 0;
char target[MAX_LEN];

int solution() {
    // Build trie
    TrieNode* root = createNode();
    for (int i = 0; i < wordCount; i++) {
        TrieNode* node = root;
        for (int j = 0; words[i][j]; j++) {
            int idx = words[i][j] - 'a';
            if (!node->children[idx]) {
                node->children[idx] = createNode();
            }
            node = node->children[idx];
        }
        node->isEnd = 1;
    }
    
    int n = strlen(target);
    int dp[n + 1];
    for (int i = 0; i <= n; i++) {
        dp[i] = (i == 0) ? 0 : INF;
    }
    
    for (int i = 0; i < n; i++) {
        if (dp[i] == INF) continue;
        
        TrieNode* node = root;
        int j = i;
        while (j < n) {
            int idx = target[j] - 'a';
            if (!node->children[idx]) break;
            node = node->children[idx];
            j++;
            if (node->isEnd && dp[i] + 1 < dp[j]) {
                dp[j] = dp[i] + 1;
            }
        }
    }
    
    return dp[n] == INF ? -1 : dp[n];
}

int main() {
    char line[2000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    char* p = strchr(line, '[') + 1;
    char* end = strrchr(line, ']');
    *end = '\0';
    
    char* token = strtok(p, ",");
    while (token != NULL && wordCount < MAX_WORDS) {
        // Remove quotes and spaces
        while (*token == ' ' || *token == '"') token++;
        int len = strlen(token);
        while (len > 0 && (token[len-1] == ' ' || token[len-1] == '"')) {
            token[len-1] = '\0';
            len--;
        }
        strcpy(words[wordCount], token);
        wordCount++;
        token = strtok(NULL, ",");
    }
    
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    int result = solution();
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × L)

n positions in target × L maximum word length for trie traversal

✓ Linear Growth

Space Complexity

O(T + n)

T nodes in trie structure + n size DP array

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

287 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

Trie + Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler