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

HardArrayStringBinary SearchDynamic ProgrammingSegment Tree

LeetCode was HARD until I Learned these 15 Patterns

13:001,002,306 views

10 video solutions available

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

Watch 10 video solutions for Minimum Number of Valid Strings to Form Target II, a hard level problem involving Array, String, Binary Search. This walkthrough by Ashish Pratap Singh has 1,002,306 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.

Problem Statement

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.

Example 1:

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

Output: 3

Explanation:

The target string can be formed by concatenating:

Prefix of length 2 of words[1], i.e. "aa".
Prefix of length 3 of words[2], i.e. "bcd".
Prefix of length 3 of words[0], i.e. "abc".

Example 2:

Input: words = ["abababab","ab"], target = "ababaababa"

Output: 2

Explanation:

The target string can be formed by concatenating:

Prefix of length 5 of words[0], i.e. "ababa".
Prefix of length 5 of words[0], i.e. "ababa".

Example 3:

Input: words = ["abcdef"], target = "xyz"

Output: -1

Constraints:

1 <= words.length <= 100
1 <= words[i].length <= 5 * 10⁴
The input is generated such that sum(words[i].length) <= 10⁵.
words[i] consists only of lowercase English letters.
1 <= target.length <= 5 * 10⁴
target consists only of lowercase English letters.

Read full problem with examples

Continue Learning

Practice this problem

Solve it on FleetCode

Read Solution & Explanation

Detailed text walkthrough

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

LeetCode was HARD until I Learned these 15 Patterns

❌ Don't Run Behind 500 LEETCODE Problems ❌ Focus on QPCD

Valid Parenthesis String - Leetcode 678 - Python

Minimum Number of Swaps to Make String Balanced - Leetcode 1963 Weekly Contest - Python

Merge Triplets to Form Target Triplet - Greedy - Leetcode 1899 - Python

Minimum Deletions to Make String Balanced - Leetcode 1653 - Python

Number of Ways to Form a Target String Given a Dictionary - Leetcode 1639 - Python

Minimum Add to Make Parentheses Valid - Leetcode 921 - Python

Leetcode Weekly Contest 415 | Video Solutions - A to D | by Harsh Gupta | TLE Eliminators

3291 Minimum Number of Valid Strings to Form Target I || How to 🤔 in Interview || Trie + Memo 🥲

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

Problem Statement

Continue Learning

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

LeetCode was HARD until I Learned these 15 Patterns

❌ Don't Run Behind 500 LEETCODE Problems ❌ Focus on QPCD

Valid Parenthesis String - Leetcode 678 - Python

Minimum Number of Swaps to Make String Balanced - Leetcode 1963 Weekly Contest - Python

Merge Triplets to Form Target Triplet - Greedy - Leetcode 1899 - Python

Minimum Deletions to Make String Balanced - Leetcode 1653 - Python

Number of Ways to Form a Target String Given a Dictionary - Leetcode 1639 - Python

Minimum Add to Make Parentheses Valid - Leetcode 921 - Python

Leetcode Weekly Contest 415 | Video Solutions - A to D | by Harsh Gupta | TLE Eliminators

3291 Minimum Number of Valid Strings to Form Target I || How to 🤔 in Interview || Trie + Memo 🥲

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

Problem Statement

Continue Learning