Facebook Pixel

3292. Minimum Number of Valid Strings to Form Target II

HardSegment TreeArrayStringBinary SearchDynamic ProgrammingString MatchingHash FunctionRolling Hash
Leetcode Link

Problem Description

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

A string x is considered valid if it is a prefix of at least one string in the words array. For example, if words = ["abc", "def"], then "a", "ab", "abc", "d", "de", "def" are all valid strings, but "b", "ac", "e" are not valid.

Your task is to find the minimum number of valid strings that can be concatenated together to form the target string. The valid strings can be used multiple times and in any order.

If it's impossible to form the target string using valid strings, return -1.

For example:

  • If words = ["abc", "ab", "def"] and target = "abcdef", you could use "abc" + "def" (2 valid strings) to form the target.
  • If words = ["a", "abc"] and target = "aaa", you could use "a" + "a" + "a" (3 valid strings) to form the target.
  • If words = ["abc"] and target = "def", it's impossible to form the target since no valid string can match any part of "def", so return -1.

The problem requires finding the optimal (minimum) way to partition the target string into segments where each segment is a valid string (prefix of some word in words).

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we need to greedily match the longest possible prefix at each position to minimize the total number of strings used.

Think of it like jumping across a river using stepping stones. At each position in the target string, we want to make the longest possible "jump" using a valid prefix. The longer each jump, the fewer total jumps we need.

For any position i in the target string, we need to find the maximum length substring starting at i that is a valid prefix of some word in words. Let's call this length f(i). For example, if at position i we can match prefixes of length 1, 2, and 5, then f(i) = 5.

The challenge is efficiently finding f(i) for each position. Since we're looking for prefixes, there's a monotonic property: if target[i..i+k] is a valid prefix, then target[i..i+j] is also valid for all j ≤ k (because a prefix of a prefix is also a prefix). This monotonicity suggests we can use binary search to find the maximum matching length.

To quickly check if a substring is a valid prefix, we can use string hashing. We precompute hash values for all prefixes of words in words and group them by length. Then, for any substring of target, we can compute its hash value and check if it exists in our precomputed set in O(1) time.

Once we can efficiently compute f(i) for each position, the problem becomes a classic greedy jumping game: starting from position 0, at each step we can jump to any position within our current reach. We want to reach the end with minimum jumps. The strategy is to always extend our reach as far as possible before making the next jump.

The algorithm tracks:

  • last: the position where we made our last jump
  • mx: the farthest position we can reach from our current range
  • When we reach last, we must make another jump to mx

If at any point last == mx and we haven't reached the end, it means we're stuck and cannot proceed further, so we return -1.

Learn more about Segment Tree, Binary Search and Dynamic Programming patterns.

Solution Implementation

1class Hashing:
2    """Rolling hash implementation for string hashing"""
3    __slots__ = ["mod", "h", "p"]
4
5    def __init__(self, s: List[str], base: int, mod: int):
6        """
7        Initialize the rolling hash for string s
8        Args:
9            s: input string as list of characters
10            base: base for polynomial rolling hash
11            mod: modulo value to prevent overflow
12        """
13        self.mod = mod
14        # h[i] stores hash value of prefix s[0:i]
15        self.h = [0] * (len(s) + 1)
16        # p[i] stores base^i mod mod
17        self.p = [1] * (len(s) + 1)
18
19        # Compute prefix hashes and powers of base
20        for i in range(1, len(s) + 1):
21            self.h[i] = (self.h[i - 1] * base + ord(s[i - 1])) % mod
22            self.p[i] = (self.p[i - 1] * base) % mod
23
24    def query(self, l: int, r: int) -> int:
25        """
26        Get hash value of substring s[l-1:r] (1-indexed)
27        Args:
28            l: left boundary (1-indexed)
29            r: right boundary (1-indexed)
30        Returns:
31            Hash value of the substring
32        """
33        return (self.h[r] - self.h[l - 1] * self.p[r - l + 1]) % self.mod
34
35
36class Solution:
37    def minValidStrings(self, words: List[str], target: str) -> int:
38        """
39        Find minimum number of valid strings needed to form target
40        Args:
41            words: list of valid word strings
42            target: target string to form
43        Returns:
44            Minimum number of valid strings, or -1 if impossible
45        """
46        def find_max_prefix_match(start_index: int) -> int:
47            """
48            Binary search to find maximum length of prefix match starting at start_index.
49            Uses template: find first length where match fails.
50            Args:
51                start_index: starting position in target string
52            Returns:
53                Maximum length of matching prefix
54            """
55            left, right = 1, min(target_length - start_index, max_word_length)
56            first_fail_index = -1
57
58            while left <= right:
59                mid = (left + right) // 2
60                # Get hash of substring from target
61                substring_hash = target_hashing.query(start_index + 1, start_index + mid)
62
63                # Feasible: this length does NOT match (first failure)
64                if substring_hash not in hash_sets[mid]:
65                    first_fail_index = mid
66                    right = mid - 1  # Found failure, look for earlier
67                else:
68                    left = mid + 1  # Still matches, try longer
69
70            # If no failure found, all lengths match
71            if first_fail_index == -1:
72                return min(target_length - start_index, max_word_length)
73            return max(0, first_fail_index - 1)
74
75        # Hash parameters
76        BASE = 13331
77        MOD = 998244353
78
79        # Initialize hashing for target string
80        target_hashing = Hashing(target, BASE, MOD)
81        target_length = len(target)
82
83        # Find maximum word length
84        max_word_length = max(len(word) for word in words)
85
86        # hash_sets[i] contains all hashes of prefixes of length i from all words
87        hash_sets = [set() for _ in range(max_word_length + 1)]
88
89        # Precompute hashes for all prefixes of all words
90        for word in words:
91            hash_value = 0
92            for length, char in enumerate(word, 1):
93                hash_value = (hash_value * BASE + ord(char)) % MOD
94                hash_sets[length].add(hash_value)
95
96        # Greedy approach: always take the longest possible match
97        answer = 0
98        last_covered = 0  # Last position that must be covered in current step
99        max_reachable = 0  # Maximum position reachable so far
100
101        for current_pos in range(target_length):
102            # Find longest match starting at current position
103            match_length = find_max_prefix_match(current_pos)
104            max_reachable = max(max_reachable, current_pos + match_length)
105
106            # If we've reached the last covered position, we need a new string
107            if current_pos == last_covered:
108                # Check if we can't progress further
109                if current_pos == max_reachable:
110                    return -1
111
112                # Use one more string and update last covered position
113                last_covered = max_reachable
114                answer += 1
115
116        return answer
117
1/**
2 * Rolling hash implementation for efficient substring hashing
3 */
4class Hashing {
5    private final long[] power;      // power[i] = base^i mod mod
6    private final long[] hash;       // hash[i] = hash value of substring [0, i)
7    private final long mod;          // modulo value for hash computation
8
9    /**
10     * Initialize the hashing structure for a given string
11     * @param word The string to preprocess for hashing
12     * @param base The base for polynomial rolling hash
13     * @param mod The modulo value to prevent overflow
14     */
15    public Hashing(String word, long base, int mod) {
16        int n = word.length();
17        power = new long[n + 1];
18        hash = new long[n + 1];
19        power[0] = 1;
20        this.mod = mod;
21
22        // Precompute powers of base and prefix hashes
23        for (int i = 1; i <= n; i++) {
24            power[i] = power[i - 1] * base % mod;
25            hash[i] = (hash[i - 1] * base + word.charAt(i - 1)) % mod;
26        }
27    }
28
29    /**
30     * Query the hash value of substring [l-1, r-1] (1-indexed input)
31     * @param l Start position (1-indexed)
32     * @param r End position (1-indexed)
33     * @return Hash value of the substring
34     */
35    public long query(int l, int r) {
36        // Calculate hash of substring using prefix hashes
37        return (hash[r] - hash[l - 1] * power[r - l + 1] % mod + mod) % mod;
38    }
39}
40
41class Solution {
42    private Hashing targetHashing;           // Hashing structure for the target string
43    private Set<Long>[] prefixHashSets;      // prefixHashSets[i] stores all hash values of prefixes of length i
44
45    /**
46     * Find minimum number of valid strings needed to form the target
47     * @param words Array of valid strings that can be used
48     * @param target The target string to form
49     * @return Minimum number of strings needed, or -1 if impossible
50     */
51    public int minValidStrings(String[] words, String target) {
52        // Hash function parameters
53        int base = 13331;
54        int mod = 998244353;
55
56        // Initialize hashing for target string
57        targetHashing = new Hashing(target, base, mod);
58
59        // Find maximum word length
60        int maxWordLength = Arrays.stream(words).mapToInt(String::length).max().orElse(0);
61
62        // Initialize hash sets for each prefix length
63        prefixHashSets = new Set[maxWordLength + 1];
64        Arrays.setAll(prefixHashSets, k -> new HashSet<>());
65
66        // Store hash values of all prefixes of all words
67        for (String word : words) {
68            long hashValue = 0;
69            for (int j = 0; j < word.length(); j++) {
70                hashValue = (hashValue * base + word.charAt(j)) % mod;
71                prefixHashSets[j + 1].add(hashValue);
72            }
73        }
74
75        // Greedy approach to find minimum strings needed
76        int answer = 0;
77        int lastCoveredPosition = 0;      // Last position where we added a new string
78        int maxReachablePosition = 0;     // Maximum position reachable from current coverage
79        int targetLength = target.length();
80
81        for (int i = 0; i < targetLength; i++) {
82            // Find longest matching prefix starting at position i
83            int longestMatch = findLongestMatchingPrefix(i, targetLength, maxWordLength);
84            maxReachablePosition = Math.max(maxReachablePosition, i + longestMatch);
85
86            // If we've reached the last covered position, we need a new string
87            if (i == lastCoveredPosition) {
88                if (i == maxReachablePosition) {
89                    // Cannot progress further - target cannot be formed
90                    return -1;
91                }
92                lastCoveredPosition = maxReachablePosition;
93                answer++;
94            }
95        }
96
97        return answer;
98    }
99
100    /**
101     * Find the longest prefix of any word that matches the target starting at position i.
102     * Uses template: find first length where match fails.
103     * @param startPos Starting position in target string
104     * @param targetLength Total length of target string
105     * @param maxWordLength Maximum length among all words
106     * @return Length of longest matching prefix
107     */
108    private int findLongestMatchingPrefix(int startPos, int targetLength, int maxWordLength) {
109        int left = 1;
110        int right = Math.min(targetLength - startPos, maxWordLength);
111        int firstFailIndex = -1;
112
113        // Binary search for the first length where match fails
114        while (left <= right) {
115            int mid = left + (right - left) / 2;
116
117            // Get hash of substring from target starting at startPos with length mid
118            long substringHash = targetHashing.query(startPos + 1, startPos + mid);
119
120            // Feasible: this length does NOT match (first failure)
121            if (!prefixHashSets[mid].contains(substringHash)) {
122                firstFailIndex = mid;
123                right = mid - 1;  // Found failure, look for earlier
124            } else {
125                left = mid + 1;  // Still matches, try longer
126            }
127        }
128
129        // If no failure found, all lengths match
130        if (firstFailIndex == -1) {
131            return Math.min(targetLength - startPos, maxWordLength);
132        }
133        return Math.max(0, firstFailIndex - 1);
134    }
135}
136
1class Hashing {
2private:
3    vector<long long> power;        // power[i] = base^i mod modulo
4    vector<long long> prefixHash;   // prefixHash[i] = hash of word[0..i-1]
5    long long modulo;
6
7public:
8    // Constructor: builds rolling hash for the given word
9    Hashing(const string& word, long long base, int modulo) {
10        int n = word.size();
11        power.resize(n + 1);
12        prefixHash.resize(n + 1);
13        power[0] = 1;
14        this->modulo = modulo;
15
16        // Precompute powers of base and prefix hashes
17        for (int i = 1; i <= n; i++) {
18            power[i] = (power[i - 1] * base) % modulo;
19            prefixHash[i] = (prefixHash[i - 1] * base + word[i - 1]) % modulo;
20        }
21    }
22
23    // Get hash of substring from index l-1 to r-1 (1-indexed query)
24    long long query(int l, int r) {
25        // Calculate hash of substring using prefix hashes
26        return (prefixHash[r] - prefixHash[l - 1] * power[r - l + 1] % modulo + modulo) % modulo;
27    }
28};
29
30class Solution {
31public:
32    int minValidStrings(vector<string>& words, string target) {
33        // Hash parameters
34        const int BASE = 13331;
35        const int MODULO = 998244353;
36
37        // Build rolling hash for target string
38        Hashing targetHashing(target, BASE, MODULO);
39
40        int maxWordLength = 0;
41        int targetLength = target.size();
42
43        // Find maximum word length
44        for (const string& word : words) {
45            maxWordLength = max(maxWordLength, (int)word.size());
46        }
47
48        // hashSets[i] contains all hashes of prefixes of length i from all words
49        vector<unordered_set<long long>> hashSets(maxWordLength + 1);
50
51        // Build hash sets for all prefixes of all words
52        for (const string& word : words) {
53            long long hash = 0;
54            for (int j = 0; j < word.size(); j++) {
55                hash = (hash * BASE + word[j]) % MODULO;
56                hashSets[j + 1].insert(hash);
57            }
58        }
59
60        // Binary search to find longest matching prefix starting at position i
61        // Uses template: find first length where match fails
62        auto findLongestMatch = [&](int startPos) -> int {
63            int left = 1;
64            int right = min(targetLength - startPos, maxWordLength);
65            int firstFailIndex = -1;
66
67            while (left <= right) {
68                int mid = left + (right - left) / 2;
69                long long substringHash = targetHashing.query(startPos + 1, startPos + mid);
70
71                // Feasible: this length does NOT match (first failure)
72                if (!hashSets[mid].count(substringHash)) {
73                    firstFailIndex = mid;
74                    right = mid - 1;  // Found failure, look for earlier
75                } else {
76                    left = mid + 1;  // Still matches, try longer
77                }
78            }
79
80            // If no failure found, all lengths match
81            if (firstFailIndex == -1) {
82                return min(targetLength - startPos, maxWordLength);
83            }
84            return max(0, firstFailIndex - 1);
85        };
86
87        // Greedy algorithm: jump to farthest reachable position
88        int minStrings = 0;
89        int currentEnd = 0;      // End of current jump range
90        int farthestReach = 0;   // Farthest position reachable
91
92        for (int i = 0; i < targetLength; i++) {
93            // Find longest match starting at position i
94            int matchLength = findLongestMatch(i);
95            farthestReach = max(farthestReach, i + matchLength);
96
97            // If we've reached the end of current jump range
98            if (i == currentEnd) {
99                // Check if we can't progress further
100                if (i == farthestReach) {
101                    return -1;  // Impossible to cover entire target
102                }
103                // Make a jump to the farthest reachable position
104                currentEnd = farthestReach;
105                minStrings++;
106            }
107        }
108
109        return minStrings;
110    }
111};
112
1// Global variables for hashing
2let power: number[] = [];        // power[i] = base^i mod modulo
3let prefixHash: number[] = [];   // prefixHash[i] = hash of word[0..i-1]
4let modulo: number;
5
6// Initialize rolling hash for the given word
7function initializeHashing(word: string, base: number, mod: number): void {
8    const n = word.length;
9    power = new Array(n + 1);
10    prefixHash = new Array(n + 1);
11    power[0] = 1;
12    modulo = mod;
13    prefixHash[0] = 0;
14
15    // Precompute powers of base and prefix hashes
16    for (let i = 1; i <= n; i++) {
17        power[i] = (power[i - 1] * base) % modulo;
18        prefixHash[i] = (prefixHash[i - 1] * base + word.charCodeAt(i - 1)) % modulo;
19    }
20}
21
22// Get hash of substring from index l-1 to r-1 (1-indexed query)
23function queryHash(l: number, r: number): number {
24    // Calculate hash of substring using prefix hashes
25    const hashValue = (prefixHash[r] - prefixHash[l - 1] * power[r - l + 1] % modulo + modulo) % modulo;
26    return hashValue;
27}
28
29function minValidStrings(words: string[], target: string): number {
30    // Hash parameters
31    const BASE = 13331;
32    const MODULO = 998244353;
33
34    // Build rolling hash for target string
35    initializeHashing(target, BASE, MODULO);
36
37    let maxWordLength = 0;
38    const targetLength = target.length;
39
40    // Find maximum word length
41    for (const word of words) {
42        maxWordLength = Math.max(maxWordLength, word.length);
43    }
44
45    // hashSets[i] contains all hashes of prefixes of length i from all words
46    const hashSets: Set<number>[] = new Array(maxWordLength + 1);
47    for (let i = 0; i <= maxWordLength; i++) {
48        hashSets[i] = new Set<number>();
49    }
50
51    // Build hash sets for all prefixes of all words
52    for (const word of words) {
53        let hash = 0;
54        for (let j = 0; j < word.length; j++) {
55            hash = (hash * BASE + word.charCodeAt(j)) % MODULO;
56            hashSets[j + 1].add(hash);
57        }
58    }
59
60    // Binary search to find longest matching prefix starting at position startPos
61    // Uses template: find first length where match fails
62    const findLongestMatch = (startPos: number): number => {
63        let left = 1;
64        let right = Math.min(targetLength - startPos, maxWordLength);
65        let firstFailIndex = -1;
66
67        while (left <= right) {
68            const mid = Math.floor((left + right) / 2);
69            const substringHash = queryHash(startPos + 1, startPos + mid);
70
71            // Feasible: this length does NOT match (first failure)
72            if (!hashSets[mid].has(substringHash)) {
73                firstFailIndex = mid;
74                right = mid - 1;  // Found failure, look for earlier
75            } else {
76                left = mid + 1;  // Still matches, try longer
77            }
78        }
79
80        // If no failure found, all lengths match
81        if (firstFailIndex === -1) {
82            return Math.min(targetLength - startPos, maxWordLength);
83        }
84        return Math.max(0, firstFailIndex - 1);
85    };
86
87    // Greedy algorithm: jump to farthest reachable position
88    let minStrings = 0;
89    let currentEnd = 0;      // End of current jump range
90    let farthestReach = 0;   // Farthest position reachable
91
92    for (let i = 0; i < targetLength; i++) {
93        // Find longest match starting at position i
94        const matchLength = findLongestMatch(i);
95        farthestReach = Math.max(farthestReach, i + matchLength);
96
97        // If we've reached the end of current jump range
98        if (i === currentEnd) {
99            // Check if we can't progress further
100            if (i === farthestReach) {
101                return -1;  // Impossible to cover entire target
102            }
103            // Make a jump to the farthest reachable position
104            currentEnd = farthestReach;
105            minStrings++;
106        }
107    }
108
109    return minStrings;
110}
111

Solution Approach

The solution implements the intuition using string hashing, binary search, and greedy strategy. Let's walk through each component:

1. String Hashing Setup

First, we create a Hashing class to efficiently compute hash values of any substring of target:

  • Uses polynomial rolling hash with base 13331 and modulo 998244353
  • Precomputes prefix hashes h[i] and powers p[i] for the target string
  • The query(l, r) method returns the hash value of target[l-1..r-1] in O(1) time using the formula: (h[r] - h[l-1] * p[r-l+1]) % mod

2. Preprocessing Word Prefixes

We build a data structure to quickly check if a substring is a valid prefix:

s = [set() for _ in range(m + 1)]  # s[i] contains hash values of all prefixes of length i

For each word in words, we compute hash values of all its prefixes and store them in s grouped by length:

  • For word "abc", we store hash("a") in s[1], hash("ab") in s[2], hash("abc") in s[3]
  • This allows O(1) lookup to check if a substring of given length is a valid prefix

3. Binary Search for Maximum Match Length

The function f(i) finds the maximum length of valid prefix starting at position i. We use the standard binary search template by finding the first length where matching fails:

def f(i: int) -> int:
    left, right = 1, min(n - i, m)
    first_fail_index = -1

    while left <= right:
        mid = (left + right) // 2
        sub = hashing.query(i + 1, i + mid)
        if sub not in s[mid]:  # feasible: this length does NOT match
            first_fail_index = mid
            right = mid - 1  # found failure, look for earlier failure
        else:
            left = mid + 1  # still matches, try longer

    # If no failure found, all lengths match up to max
    # Otherwise, return first_fail_index - 1 (last matching length)
    if first_fail_index == -1:
        return min(n - i, m)
    return max(0, first_fail_index - 1)

The binary search exploits the monotonic property: lengths that fail to match form a pattern [false, false, ..., true, true, ...] where true means "no match".

4. Greedy Jump Strategy

With f(i) computed for each position, we solve the minimum jumps problem:

ans = last = mx = 0
for i in range(n):
    dist = f(i)
    mx = max(mx, i + dist)  # update the farthest reachable position

    if i == last:  # reached the end of current jump range
        if i == mx:  # cannot move further
            return -1
        last = mx  # make a new jump to the farthest position
        ans += 1

The algorithm maintains:

  • last: the position where we must make the next jump
  • mx: the farthest position reachable from current range
  • ans: the number of jumps made

At each position i, we:

  1. Calculate how far we can jump from i using f(i)
  2. Update the maximum reachable position mx
  3. If we reach last, we must jump again:
    • If last == mx, we're stuck (return -1)
    • Otherwise, jump to mx and increment the answer

Time Complexity

  • Preprocessing: O(L) where L is the total length of all words
  • For each position in target: O(log m) for binary search with O(1) hash checks
  • Total: O(L + n log m) where n is the length of target and m is the maximum word length

Space Complexity

  • O(L) for storing hash values of all prefixes
  • O(n) for the hashing data structure of target

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example: words = ["abc", "ab", "def"] and target = "abdef"

Step 1: Preprocessing - Build Hash Sets for Valid Prefixes

First, we compute hash values for all prefixes of words in words:

  • From "abc": hash("a") → s[1], hash("ab") → s[2], hash("abc") → s[3]
  • From "ab": hash("a") → s[1], hash("ab") → s[2]
  • From "def": hash("d") → s[1], hash("de") → s[2], hash("def") → s[3]

Our hash sets become:

  • s[1] = {hash("a"), hash("d")}
  • s[2] = {hash("ab"), hash("de")}
  • s[3] = {hash("abc"), hash("def")}

Step 2: Compute Maximum Match Length at Each Position

For each position i in target = "abdef", we use binary search to find f(i):

  • i = 0 (looking at "abdef"):

    • Binary search range: [0, 5]
    • Check mid=3: "abd" → NOT in s[3] → search [0, 2]
    • Check mid=2: "ab" → IS in s[2] → search [2, 2]
    • Result: f(0) = 2 (can match "ab")

  • i = 1 (looking at "bdef"):

    • Binary search range: [0, 4]
    • Check mid=2: "bd" → NOT in s[2] → search [0, 1]
    • Check mid=1: "b" → NOT in s[1] → search [0, 0]
    • Result: f(1) = 0 (no valid prefix starts with "b")

  • i = 2 (looking at "def"):

    • Binary search range: [0, 3]
    • Check mid=2: "de" → IS in s[2] → search [2, 3]
    • Check mid=3: "def" → IS in s[3] → search [3, 3]
    • Result: f(2) = 3 (can match "def")

  • i = 3 (looking at "ef"):

    • Binary search range: [0, 2]
    • Check mid=1: "e" → NOT in s[1] → search [0, 0]
    • Result: f(3) = 0 (no valid prefix starts with "e")

  • i = 4 (looking at "f"):

    • Binary search range: [0, 1]
    • Check mid=1: "f" → NOT in s[1] → search [0, 0]
    • Result: f(4) = 0 (no valid prefix starts with "f")

Step 3: Greedy Jump Strategy

Now we simulate the jumping process:

Initial state: ans = 0, last = 0, mx = 0

  • i = 0:

    • f(0) = 2, so from position 0 we can reach position 0+2 = 2
    • Update: mx = max(0, 2) = 2
    • Since i == last (both 0), we need to jump:
      • last ≠ mx (0 ≠ 2), so we can proceed
      • Update: last = 2, ans = 1
      • We've made our first jump, using "ab" to cover positions [0,1]

  • i = 1:

    • f(1) = 0, so from position 1 we can't jump anywhere
    • mx remains 2
    • i < last (1 < 2), so no jump needed yet

  • i = 2:

    • f(2) = 3, so from position 2 we can reach position 2+3 = 5
    • Update: mx = max(2, 5) = 5
    • Since i == last (both 2), we need to jump:
      • last ≠ mx (2 ≠ 5), so we can proceed
      • Update: last = 5, ans = 2
      • We've made our second jump, using "def" to cover positions [2,4]

  • i = 3 and i = 4:

    • Both have f(i) = 0
    • mx remains 5
    • i < last, so no jumps needed

Final result: We've reached the end (position 5) with ans = 2 jumps.

The solution correctly identifies that we need 2 valid strings: "ab" + "def" = "abdef"

Key Insights from the Example:

  1. The binary search efficiently finds the longest valid prefix at each position
  2. The greedy strategy ensures we make the minimum number of jumps by always extending our reach as far as possible
  3. Positions where f(i) = 0 (like positions 1, 3, 4) don't affect the result as long as they're covered by previous jumps

Time and Space Complexity

Time Complexity: O(n × log n + L)

The time complexity breaks down as follows:

  • Building the hash sets for all prefixes of words takes O(L) time, where L is the total length of all words
  • The main loop iterates through each position in the target string (n iterations)
  • For each position i, the function f(i) performs a binary search:
    • The binary search range is from 0 to min(n - i, m), where m is the maximum word length
    • Each binary search iteration calls hashing.query() which runs in O(1) time
    • The binary search takes O(log min(n - i, m)) which is bounded by O(log n)
  • Therefore, the total time for all binary searches is O(n × log n)
  • Overall time complexity: O(n × log n + L)

Space Complexity: O(n + L)

The space complexity consists of:

  • The Hashing class stores two arrays h and p, each of size n + 1, using O(n) space
  • The hash sets s store hash values for all prefixes of all words:
    • There are at most m + 1 sets
    • The total number of hash values stored across all sets is bounded by the total length of all words L
    • This uses O(L) space
  • Other variables (ans, last, mx, etc.) use O(1) space
  • Overall space complexity: O(n + L)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid instead of the standard template with while left <= right and right = mid - 1.

Pitfall Code:

def find_max_prefix_match(start_index: int) -> int:
    # WRONG: Non-standard template variant
    left, right = 0, min(target_length - start_index, max_word_length)
    while left < right:
        mid = (left + right + 1) >> 1
        if substring_hash in hash_sets[mid]:
            left = mid
        else:
            right = mid - 1
    return left

Why it's problematic:

  • Different template variants are error-prone and harder to verify
  • The +1 in (left + right + 1) >> 1 is easy to forget

Solution: Use the standard template by finding the first failure:

def find_max_prefix_match(start_index: int) -> int:
    left, right = 1, min(target_length - start_index, max_word_length)
    first_fail_index = -1

    while left <= right:
        mid = (left + right) // 2
        if substring_hash not in hash_sets[mid]:  # Feasible: no match
            first_fail_index = mid
            right = mid - 1
        else:
            left = mid + 1

    if first_fail_index == -1:
        return min(target_length - start_index, max_word_length)
    return max(0, first_fail_index - 1)

2. Hash Collision Not Considered

While the code uses a large prime modulo (998244353), hash collisions can still occur in edge cases, leading to false positive matches.

Pitfall: Relying on a single hash function without verification.

Solution: Use double hashing or verify matches with actual string comparison:

# Enhanced version with double hashing
class DoubleHashing:
    def __init__(self, s, base1=13331, mod1=998244353, base2=31, mod2=10**9+7):
        self.hash1 = Hashing(s, base1, mod1)
        self.hash2 = Hashing(s, base2, mod2)

    def query(self, l, r):
        return (self.hash1.query(l, r), self.hash2.query(l, r))

3. Incorrect Greedy Jump Logic

A subtle but critical error occurs when updating the jump position without properly checking if progress is being made.

Pitfall Code:

for current_pos in range(target_length):
    match_length = find_max_prefix_match(current_pos)
    max_reachable = max(max_reachable, current_pos + match_length)

    if current_pos == last_covered:
        # WRONG: Not checking if we're stuck before incrementing answer
        last_covered = max_reachable
        answer += 1

Why it's wrong:

  • This would increment answer even when max_reachable equals current_pos (no progress)
  • Results in returning a positive number instead of -1 for impossible cases

Solution:

if current_pos == last_covered:
    # CORRECT: Check if we're stuck first
    if current_pos == max_reachable:
        return -1  # Cannot progress further
    last_covered = max_reachable
    answer += 1

4. Empty Words or Target Edge Cases

The code doesn't explicitly handle edge cases like empty strings in the words array or empty target.

Pitfall: Not validating input can cause unexpected behavior.

Solution:

def minValidStrings(self, words: List[str], target: str) -> int:
    # Add input validation
    if not target:
        return 0
    if not words or all(not word for word in words):
        return -1

    # Filter out empty words
    words = [word for word in words if word]
    if not words:
        return -1

    # Continue with main logic...

5. Integer Overflow in Hash Computation

When computing hash values for very long strings, intermediate calculations might overflow even with modulo operations.

Pitfall Code:

# In preprocessing
hash_value = (hash_value * BASE + ord(char)) % MOD

Why it's a concern:

  • Python handles big integers automatically, but in other languages this could overflow
  • Even in Python, very large intermediate values can slow down computation

Solution:

# More careful modulo application
hash_value = ((hash_value * BASE) % MOD + ord(char)) % MOD

These pitfalls highlight the importance of careful boundary condition handling, proper validation, and understanding the nuances of the greedy approach in this problem.

Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Vanilla Binary Search

https assets algo monster cover_photos Binary_Search svg Binary Search Intuition Binary search is an efficient array search algorithm It works by narrowing down the search range by half each time If you have looked up a word in a physical dictionary you've already used binary search in real life Let's

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More