Leetcode 2781 - Length of the Longest Valid Substring

Table of Contents

Problem

Given a string word and an array of strings forbidden, find the length of the longest valid substring of word. A string is considered valid if none of its substrings are present in forbidden.

Example 1:

Input: word = "cbaaaabc", forbidden = ["aaa","cb"]
Output: 4
Explanation: The longest valid substring is "aabc".

Example 2:

Input: word = "leetcode", forbidden = ["de","le","e"]
Output: 4
Explanation: The longest valid substring is "tcod".

Constraints:

• 1 <= word.length <= 10^5
• 1 <= forbidden.length <= 10^5
• 1 <= forbidden[i].length <= 10
• word and forbidden[i] consist only of lowercase English letters.

Explanation/Approach

This problem can be approached using Dynamic Programming (DP). We will use a DP array to store the length of the longest valid substring that ends at each index in word.

Approach 1: Dynamic Programming

• DP Array Initialization: Initialize a DP array dp of length n (length of word), where dp[i] denotes the longest valid substring that ends at index i.
• Forbidden Set: Convert forbidden into a set for faster queries.
• Iterating Over word: For each character in word, calculate dp[i] by checking every possible substring ending at that character against the forbidden set.
• Updating dp[i]: The value of dp[i] is the minimum of the length of the substring until a match in forbidden is found, and dp[i - 1] + 1.
• Result: The maximum value in dp is the length of the longest valid substring.

Approach 2: Space-Optimized Dynamic Programming

• Space Optimization: Use variables prev, curr, and ans to represent dp[i - 1], dp[i], and the maximum value of dp so far, respectively.
• Algorithm: Follow the same steps as the first approach, but only keep track of the last and current DP values and the maximum answer.

Solution 1: Dynamic Programming

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        # Length of the input word
        n = len(word)

        # Convert the forbidden list into a set for faster lookup
        forbidden = set(forbidden)

        # Initialize the DP array where dp[i] will store the length of
        # the longest valid substring ending at index i.
        # Initially, it is optimistically set to the maximum possible value (i + 1)
        dp = list(range(1, n + 1))

        # Iterate over each character in the word
        for i in range(n):
            # Check each substring that ends at index i
            # The inner loop checks substrings of length up to 10 (maximum length of forbidden strings)
            for j in range(10):
                # Break if the start index of the substring is negative
                if i - j < 0:
                    break
                # If the substring is in forbidden, update dp[i] to the length of this substring
                # This indicates the last part of the word that cannot be included in a valid substring
                if word[i - j : i + 1] in forbidden:
                    dp[i] = j
                    break

            # Additionally, dp[i] is also bounded by dp[i - 1] + 1
            # This ensures that we don't count any additional length beyond what was valid till the previous character
            if i > 0:
                dp[i] = min(dp[i], dp[i - 1] + 1)

        # The maximum value in the DP array represents the length of the longest valid substring
        return max(dp)

Visual Representation

1. DP Array Initialization:

   • Start with dp = [1, 2, 3, ..., n] for word of length n.

2. Iterating and Updating DP Array:

   • For each character in word, check every substring ending at this character.
   • If a substring matches a forbidden string, update dp[i].
   • Example: word = "cbaaaabc", forbidden = ["aaa","cb"]
     • At index 3 (character ‘a’), substring “cbaa” is checked. Since “cb” is forbidden, dp[3] is updated.

3. Visual Example:

   • word = "cbaaaabc", forbidden = ["aaa","cb"]
   • dp = [1, 2, 3, 2, 1, 2, 3, 4]
   • Each element in dp represents the longest valid substring ending at that index.

4. Final Result:

   • The maximum value in dp is the answer. In this case, max(dp) = 4.

Solution 2: Space-Optimized Dynamic Programming

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
        n = len(word)
        forbidden = set(forbidden)
        ans = prev = 0
        for i in range(n):
            curr = i + 1
            for j in range(10):
                if i - j < 0:
                    break
                if word[i - j : i + 1] in forbidden:
                    curr = j
                    break
            curr = min(curr, prev + 1)
            ans = max(ans, curr)
            prev = curr
        return ans

Time and Memory Complexity

• Time Complexity: O(L + nm^2), where L is the total length of the forbidden strings, n is the length of word, and m is the maximum length of the forbidden strings.
• Space Complexity:
  • For Solution 1: O(L + n), where L is the total length of the forbidden strings, and n is the length of

word.

• For Solution 2: O(L), where L is the total length of the forbidden strings.

Visual Representation Approach 2: Space-Optimized Dynamic Programming

1. Using Variables prev, curr, and ans:

   • prev represents dp[i - 1], curr represents dp[i], and ans is the maximum length so far.

2. Iterating and Updating Variables:

   • Similar to Approach 1, but only keeping track of the last and current DP values and the maximum answer.
   • Example: word = "cbaaaabc", forbidden = ["aaa","cb"]
     • When at index 3, prev = 3, curr is updated based on the forbidden substring.

3. Visual Example:

   • word = "cbaaaabc", forbidden = ["aaa","cb"]
   • Iteration:
     • At index 2, prev = 3, curr = 2, ans = 3
     • At index 3, prev = 2, curr = 1, ans = 3
     • And so on.

4. Final Result:

   • The maximum length of a valid substring is stored in ans. In this case, ans = 4.

In both approaches, the key is to dynamically adjust the length of the valid substring based on the presence of forbidden substrings and update the maximum length found so far. The space-optimized version achieves the same result with less memory usage by only keeping track of the necessary previous state.