#2781

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Length of the Longest Valid Substring

This problem asks for the longest valid substring of a word that doesn't contain any substrings from a forbidden list.

Problem Statement

You are given a string word and an array of forbidden strings. A substring of word is valid if it does not contain any of the forbidden strings as a part of it. You need to return the length of the longest valid substring within word.

To solve the problem, we must scan through the string word and check for the presence of any forbidden substring in each potential substring. Efficient array scanning and hash lookups help to avoid recalculating substrings multiple times, ensuring an optimal solution.

Examples

Example 1

Input: word = "cbaaaabc", forbidden = ["aaa","cb"]

Output: 4

There are 11 valid substrings in word: "c", "b", "a", "ba", "aa", "bc", "baa", "aab", "ab", "abc" and "aabc". The length of the longest valid substring is 4. It can be shown that all other substrings contain either "aaa" or "cb" as a substring.

Example 2

Input: word = "leetcode", forbidden = ["de","le","e"]

Output: 4

There are 11 valid substrings in word: "l", "t", "c", "o", "d", "tc", "co", "od", "tco", "cod", and "tcod". The length of the longest valid substring is 4. It can be shown that all other substrings contain either "de", "le", or "e" as a substring.

Constraints

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

Solution Approach

Sliding Window with Hash Lookup

We can use a sliding window to keep track of the current valid substring. For each position in the string, expand the window by including the next character, while checking if any forbidden substring is inside the current window using a hash table. If a forbidden substring is found, shrink the window until it becomes valid again.

Efficient Substring Validation with Hashing

Hash tables allow us to quickly check if a substring is in the forbidden list. We can hash all forbidden substrings and then use these hashes to verify if any part of the current window contains forbidden substrings. This reduces the time complexity significantly compared to a brute-force approach.

Optimized Window Management

Instead of checking every possible substring in a brute-force manner, we manage the window dynamically. This allows us to only check relevant substrings and minimize the amount of work done by discarding invalid parts of the string early.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the approach used, particularly on how we manage the sliding window and the forbidden list. In the optimal case, both time and space complexity can be reduced to O(n), where n is the length of the string, by using a hash table for forbidden substrings and dynamically adjusting the sliding window.

What Interviewers Usually Probe

Candidate demonstrates a clear understanding of array scanning and sliding window techniques.
Candidate effectively applies hash tables to optimize substring validation.
Candidate is able to balance correctness and efficiency in their solution approach.

Common Pitfalls or Variants

Common pitfalls

Incorrect window shrinking when a forbidden substring is found, leading to missed valid substrings.
Overlooking the need for efficient substring validation, leading to poor performance for large inputs.
Improper handling of the case when there are no valid substrings, which can lead to incorrect results.

Follow-up variants

Handle cases where the forbidden list is very large and requires additional optimizations.
Extend the problem to handle uppercase characters or other alphabet types.
Consider cases where all substrings are forbidden and the output should be zero.

FAQ

What is the optimal approach for solving Length of the Longest Valid Substring?

The optimal approach involves using a sliding window to keep track of the current valid substring and hash tables to quickly check forbidden substrings.

How can hash tables be used in the Length of the Longest Valid Substring problem?

Hash tables allow for constant-time lookup to determine if a substring exists in the forbidden list, speeding up the validation process.

Why is the sliding window technique important in this problem?

The sliding window technique ensures we only scan relevant substrings, reducing unnecessary checks and improving performance.

How does GhostInterview assist with solving this problem?

GhostInterview provides step-by-step problem-solving guidance and suggests optimal algorithms like sliding windows and hash lookups to solve this problem efficiently.

What should I avoid when solving the Length of the Longest Valid Substring?

Avoid using a brute-force approach to generate all possible substrings, as this will lead to time inefficiencies for large inputs.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#2799 count complete subarrays in an array #2747 count zero request servers #2744 find maximum number of string pairs