Problem Statement

Given a string word and an array of strings forbidden, return the length of the longest valid substring of the string word.

A string is called valid if none of its substrings are present in a forbidden array.

A substring is defined as a contiguous sequence of characters in a string.

Examples

• Example 1:

  • Input: word = "abracadabra", forbidden = ["cad", "abr"]
  • Expected Output: 5
  • Justification: The longest valid substring without any forbidden substrings is "braca",which is 5 characters long.

• Example 2:

  • Input: word = "sunshine", forbidden = ["sun", "shine"]
  • Expected Output: 6
  • Justification: The longest valid substring that does not include any forbidden substrings is "unshin", which is 6 characters long.

• Example 3:

  • Input: word = "openai", forbidden = ["pen", "ai"]
  • Expected Output: 3
  • Justification: The longest valid substring avoiding the forbidden substrings is "ope", which is 3 characters long.

Constraints:

• 1 <= word.length <= 10⁵
• word consists only of lowercase English letters.
• 1 <= forbidden.length <= 10⁵
• 1 <= forbidden[i].length <= 10
• forbidden[i] consists only of lowercase English letters.

Try it yourself

Try solving this question here: