We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Length of the Longest Valid Substring

Difficulty: Hard

Problem Description

You are given a string word and an array of strings forbidden. A string is called valid if none of its substrings are present in forbidden. Return the length of the longest valid substring of the string word. A substring is a contiguous sequence of characters in a string, possibly empty.

Key Insights

  • A substring is valid if it does not contain any of the strings in the forbidden list as a substring.
  • We can utilize a sliding window approach to efficiently find the longest valid substring.
  • Maintaining a set of forbidden substrings allows for quick checks to determine if the current window is valid.
  • The length of the longest valid substring can be tracked using two pointers representing the start and end of the current window.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of word and m is the total length of forbidden substrings due to substring checks in the sliding window.

Space Complexity: O(k), where k is the number of forbidden substrings stored in a set for fast lookup.

Solution

To solve this problem, we can use a sliding window technique combined with a hash set to store the forbidden substrings. We will iterate through the string, expanding the end of the window while checking if any forbidden substring exists within the current window. If a forbidden substring is found, we will contract the start of the window until the substring is no longer present. This allows us to efficiently manage the valid substring length.

Code Solutions

def longest_valid_substring(word, forbidden):
    forbidden_set = set(forbidden)
    max_length = 0
    start = 0
    end = 0
    while end < len(word):
        # Check if any forbidden substring is in the current window
        for length in range(1, 11):  # Check lengths from 1 to 10
            if end - length + 1 >= start and word[end - length + 1:end + 1] in forbidden_set:
                start = end - length + 2  # Move start past the forbidden substring
                break
        max_length = max(max_length, end - start + 1)
        end += 1
    return max_length
← Back to All Questions