Table of Contents
Open 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
andforbidden[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 lengthn
(length ofword
), wheredp[i]
denotes the longest valid substring that ends at indexi
.  Forbidden Set: Convert
forbidden
into a set for faster queries.  Iterating Over
word
: For each character inword
, calculatedp[i]
by checking every possible substring ending at that character against theforbidden
set.  Updating
dp[i]
: The value ofdp[i]
is the minimum of the length of the substring until a match inforbidden
is found, anddp[i  1] + 1
.  Result: The maximum value in
dp
is the length of the longest valid substring.
Approach 2: SpaceOptimized Dynamic Programming
 Space Optimization: Use variables
prev
,curr
, andans
to representdp[i  1]
,dp[i]
, and the maximum value ofdp
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

DP Array Initialization:
 Start with
dp = [1, 2, 3, ..., n]
forword
of lengthn
.
 Start with

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.
 At index 3 (character ‘a’), substring “cbaa” is checked. Since “cb” is forbidden,
 For each character in

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.

Final Result:
 The maximum value in
dp
is the answer. In this case,max(dp) = 4
.
 The maximum value in
Solution 2: SpaceOptimized 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: SpaceOptimized Dynamic Programming

Using Variables
prev
,curr
, andans
:prev
representsdp[i  1]
,curr
representsdp[i]
, andans
is the maximum length so far.

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.
 When at index 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.
 At index 2,

Final Result:
 The maximum length of a valid substring is stored in
ans
. In this case,ans = 4
.
 The maximum length of a valid substring is stored in
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 spaceoptimized version achieves the same result with less memory usage by only keeping track of the necessary previous state.