3291. Minimum Number of Valid Strings to Form Target I LeetCode Solution

In this guide, you will get 3291. Minimum Number of Valid Strings to Form Target I LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Valid Strings to Form Target I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Number of Valid Strings to Form Target I solution in C++
4. Minimum Number of Valid Strings to Form Target I solution in Java
5. Minimum Number of Valid Strings to Form Target I solution in Python
6. Additional Resources

Problem Statement of Minimum Number of Valid Strings to Form Target I

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 * 103
The input is generated such that sum(words[i].length) <= 105.
words[i] consists only of lowercase English letters.
1 <= target.length <= 5 * 103
target consists only of lowercase English letters.

Complexity Analysis

• Time Complexity: O(|\texttt{words}| \cdot \Sigma (|\texttt{words[i]}| + |\texttt{target}|))
• Space Complexity: O(|\texttt{words}| \cdot \Sigma (|\texttt{words[i]}| + |\texttt{target}|))

3291. Minimum Number of Valid Strings to Form Target I LeetCode Solution in C++

class Solution {
 public:
  int minValidStrings(vector<string>& words, string target) {
    int ans = 0;
    int unmatchedPrefix = target.length();
    vector<vector<int>> lpsList;

    for (const string& word : words)
      lpsList.push_back(getLPS(word + '#' + target));

    while (unmatchedPrefix > 0) {
      // Greedily choose the word that has the longest suffix match with the
      // remaining unmatched prefix.
      int maxMatchSuffix = 0;
      for (int i = 0; i < words.size(); ++i)
        maxMatchSuffix = max(maxMatchSuffix,
                             lpsList[i][words[i].length() + unmatchedPrefix]);
      if (maxMatchSuffix == 0)
        return -1;
      ++ans;
      unmatchedPrefix -= maxMatchSuffix;
    }

    return ans;
  }

 private:
  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  vector<int> getLPS(const string& pattern) {
    vector<int> lps(pattern.length());
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern[j] != pattern[i])
        j = lps[j - 1];
      if (pattern[i] == pattern[j])
        lps[i] = ++j;
    }
    return lps;
  }
};
/* code provided by PROGIEZ */

3291. Minimum Number of Valid Strings to Form Target I LeetCode Solution in Java

class Solution {
  public int minValidStrings(String[] words, String target) {
    int ans = 0;
    int unmatchedPrefix = target.length();
    int[][] lpsList = new int[words.length][];

    for (int i = 0; i < words.length; ++i)
      lpsList[i] = getLPS(words[i] + '#' + target);

    while (unmatchedPrefix > 0) {
      // Greedily choose the word that has the longest suffix match with the
      // remaining unmatched prefix.
      int maxMatchSuffix = 0;
      for (int i = 0; i < words.length; ++i)
        maxMatchSuffix = Math.max(maxMatchSuffix, lpsList[i][words[i].length() + unmatchedPrefix]);
      if (maxMatchSuffix == 0)
        return -1;
      ++ans;
      unmatchedPrefix -= maxMatchSuffix;
    }

    return ans;
  }

  // Returns the lps array, where lps[i] is the length of the longest prefix of
  // pattern[0..i] which is also a suffix of this substring.
  private int[] getLPS(final String pattern) {
    int[] lps = new int[pattern.length()];
    for (int i = 1, j = 0; i < pattern.length(); ++i) {
      while (j > 0 && pattern.charAt(j) != pattern.charAt(i))
        j = lps[j - 1];
      if (pattern.charAt(i) == pattern.charAt(j))
        lps[i] = ++j;
    }
    return lps;
  }
}
// code provided by PROGIEZ

3291. Minimum Number of Valid Strings to Form Target I LeetCode Solution in Python

class Solution:
  def minValidStrings(self, words: list[str], target: str) -> int:
    ans = 0
    unmatchedPrefix = len(target)
    lpsList = [self._getLPS(word + '#' + target) for word in words]

    while unmatchedPrefix > 0:
      # Greedily choose the word that has the longest suffix match with the
      # remaining unmatched prefix.
      maxMatchSuffix = 0
      for lps, word in zip(lpsList, words):
        maxMatchSuffix = max(maxMatchSuffix, lps[len(word) + unmatchedPrefix])
      if maxMatchSuffix == 0:
        return -1
      ans += 1
      unmatchedPrefix -= maxMatchSuffix

    return ans

  def _getLPS(self, pattern: str) -> list[int]:
    """
    Returns the lps array, where lps[i] is the length of the longest prefix of
    pattern[0..i] which is also a suffix of this substring.
    """
    lps = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
      while j > 0 and pattern[j] != pattern[i]:
        j = lps[j - 1]
      if pattern[i] == pattern[j]:
        lps[i] = j + 1
        j += 1
    return lps
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.