Minimum Number of Valid Strings to Form Target II - Video Solutions

Problem Overview: You are given a list of valid strings and a target string. The goal is to form the target by concatenating valid strings (or their prefixes depending on constraints) while minimizing the total number of strings used. If the target cannot be formed, return -1. The challenge is efficiently checking which substrings of the target match valid strings while minimizing the number of segments used.

Approach 1: Dynamic Programming with Rolling Hash (O(n log n) time, O(n) space)

The core idea is to treat the problem as a segmentation task. Define dp[i] as the minimum number of valid strings required to build the prefix target[0..i). For each position, attempt to extend using any valid substring that matches the target starting at that index. Direct string comparison would be too slow, so use rolling hash to check substring equality in constant time. Precompute hashes for the target and store hashes of valid strings by length. For each index, binary search the maximum valid match length and update the DP transition. This reduces repeated comparisons and keeps substring checks efficient.

This approach combines dynamic programming for optimal substructure and string matching techniques for fast substring validation. The DP ensures minimal segmentation while rolling hash eliminates expensive character-by-character checks.

Approach 2: Greedy with Backtracking (O(n^2) worst case time, O(n) space)

A simpler approach attempts to greedily match the longest valid string starting at the current position. If multiple matches exist, choose the longest candidate and recursively attempt to build the remainder of the target. When a greedy choice fails later, backtrack and try the next candidate. Memoization can prune repeated states by caching results for each index.

This strategy works because longer matches often reduce the total number of segments. However, greedy choices are not always globally optimal, so backtracking ensures correctness. Matching can be accelerated with prefix comparisons or pre-indexed candidate lengths. Compared to the DP solution, this method is easier to implement but may degrade in performance for large inputs with many overlapping prefixes.

The greedy/backtracking strategy relies heavily on fast prefix checks and benefits from techniques like rolling hash or prefix maps for efficient substring validation.

Recommended for interviews: The dynamic programming approach with hashing is the expected optimal solution. It demonstrates understanding of segmentation DP, efficient substring matching, and complexity optimization. Explaining the greedy strategy first helps show intuition about minimizing segments, but the DP formulation proves you can guarantee the optimal result under strict constraints.