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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Length of the Longest Valid Substring

Number: 2884

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given a string word and an array forbidden, determine the length of the longest contiguous substring of word that does not contain any substring from forbidden.

Key Insights

  • Use a sliding window approach to efficiently check for valid substrings.
  • Since every forbidden word has length at most 10, only the last 10 characters need to be checked when expanding the window.
  • Utilize a hash set for O(1) lookup of forbidden substrings.
  • Adjust the left boundary of the window when a forbidden substring is found within the current window.

Space and Time Complexity

Time Complexity: O(n * L), where n is the length of word and L is the maximum length (up to 10) of a forbidden word. Space Complexity: O(m), where m is the number of forbidden words stored in the hash set.

Solution

We apply a sliding window algorithm where we iterate through the string using a right pointer to extend the window. For each new character, only the last L characters (L = min(10, current window length)) are checked against the forbidden set. If any such substring is found in the forbidden set, the left pointer is moved ahead to exclude the forbidden substring from the current window. This ensures that the window always represents a valid substring. The maximum length encountered while sliding through the string is recorded and returned.

Code Solutions

# Python solution with detailed comments
def longestValidSubstring(word, forbidden):
    # Create a set for O(1) lookup of forbidden substrings
    forbidden_set = set(forbidden)
    
    n = len(word)
    left = 0  # left pointer for the sliding window
    max_len = 0  # to track maximum valid substring length
    
    # Iterate through the string with right pointer
    for right in range(n):
        # Check possible substrings ending at 'right' with at most 10 characters
        for l in range(1, min(10, right - left + 1) + 1):
            # Obtain the substring of length l ending at right
            if word[right - l + 1:right + 1] in forbidden_set:
                # Move the left pointer to avoid including the forbidden substring
                left = max(left, right - l + 2)
        # Update maximum length if current window is larger
        max_len = max(max_len, right - left + 1)
    return max_len

# Example usage
print(longestValidSubstring("cbaaaabc", ["aaa", "cb"]))  # Output: 4
← Back to All Questions