hard Length of the Longest Valid Substring

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.

Solution

To solve this problem, we will employ a sliding window approach combined with substring verification. This method involves expanding and contracting a window on the input string to find the longest segment that does not contain any of the forbidden substrings. The sliding window technique is chosen because it efficiently examines all possible substrings without redundant checks, making it ideal for this task.

Initially, we'll consider every possible starting point of a substring within the input string. For each start point, we'll expand the window to the right until we encounter a substring that matches any forbidden string. Upon finding such a match, we'll contract the window from the left to exclude the forbidden substring and continue the process. This approach ensures that we explore all potential substrings while skipping over invalid regions quickly, thereby identifying the maximum valid substring length.

Step-by-step Algorithm

• Initialize two pointers, left and right, to traverse the string. left will mark the start of the current substring, and right will mark the end.
• Initialize a variable maxLength to keep track of the maximum length of valid substrings found.
• Use a nested loop where the outer loop moves left from the beginning to the end of the string, and the inner loop expands right as long as the current substring does not contain any forbidden substrings.
  • For each position of left, reset right to left and incrementally expand right to explore all possible substrings starting from left.
  • Check if the current substring (word.substring(left, right + 1)) contains any forbidden substring. If it does, break the inner loop since expanding further will also include the forbidden substring.
  • Update maxLength if the length of the current valid substring (right - left) is greater than the current maxLength.
• Continue this process until all substrings have been examined.
• The final value of maxLength after the loops complete is the length of the longest valid substring.

Algorithm Walkthrough

Let's consider the input word = "sunshine" and forbidden = ["sun", "shine"].

1. Initialize maxLength: Start with maxLength set to 0. This variable will hold the length of the longest valid substring found that does not contain any forbidden substrings.

2. First Iteration (i = 0, starting with "s"):

   • Generate substrings starting from "s": "s", "su", "sun", "suns", "sunsh", "sunshi", "sunshin", "sunshine".
     • "s" is valid, update maxLength to 1.
     • "su" is valid, update maxLength to 2.
     • "sun" is invalid (matches a forbidden word), break the inner loop.

3. Second Iteration (i = 1, starting with "u"):

   • Generate substrings: "u", "un", "uns", "unsh", "unshi", "unshin", "unshine".
     • "u" is valid, but no update since its length is less than maxLength.
     • "un" is valid, but no update for the same reason.
     • "uns" is valid, update maxLength to 3.
     • "unsh" is valid, update maxLength to 4.
     • "unshi" is valid, update maxLength to 5.
     • "unshin" is valid, update maxLength to 6.
     • "unshine" is invalid (contains "shine"), break the inner loop.

4. Third Iteration (i = 2, starting with "n"):

   • Generate substrings: "n", "ns", "nsh", "nshi", "nshin", "nshine".
     • "n" is valid, but no update since its length is less than maxLength.
     • Continue with "ns", "nsh", "nshi", "nshin", all valid but shorter than current maxLength.
     • "nshine" is invalid (contains "shine"), break the inner loop.

5. Fourth Iteration (i = 3, starting with "s"):

   • Generate substrings: "s", "sh", "shi", "shin", "shine".
     • All substrings are valid until "shine", which is invalid. However, none are longer than the current maxLength of 6.

6. Subsequent Iterations:

   • For i = 4 (starting with "h") and onwards, all possible substrings are shorter than the current maxLength or become invalid once "shine" is included.

7. Fifth Iteration (i = 4, starting with "h"):

   • Substrings: "h", "hi", "hin", "hine". None surpass the maxLength.

8. Sixth Iteration (i = 5, starting with "i"):

   • Substrings: "i", "in", "ine". Again, none are longer than maxLength.

9. Seventh Iteration (i = 6, starting with "n"):

   • Substrings: "n", "ne". Neither are longer than maxLength.

10. Eighth Iteration (i = 7, starting with "e"):

    • Only substring: "e". Does not exceed maxLength.

11. Conclusion:

    • maxLength is finalized as 6.

Code

public class Solution {

  // Method to find the length of the longest valid substring
  public int findLengthOfLongestValidSubstring(
    String word,
    String[] forbidden
  ) {
    int maxLength = 0; // Variable to store the maximum valid substring length found
    // Iterate through each possible starting point of the substring
    for (int left = 0; left < word.length(); ++left) {
      // Iterate through each possible ending point of the substring
      for (int right = left; right < word.length(); ++right) {
        String currentSubstring = word.substring(left, right + 1);
        // Break the inner loop if the current substring is forbidden
        if (isForbidden(currentSubstring, forbidden)) break;
        // Update the maxLength if the current substring is longer than previous ones
        maxLength = Math.max(maxLength, right - left + 1);
      }
    }
    return maxLength; // Return the length of the longest valid substring found
  }

  // Helper function to check if a substring contains any forbidden string
  boolean isForbidden(String substring, String[] forbidden) {
    for (String forb : forbidden) {
      if (substring.contains(forb)) return true;
    }
    return false;
  }

  // Main method to test the functionality
  public static void main(String[] args) {
    Solution solution = new Solution();
    System.out.println(
      solution.findLengthOfLongestValidSubstring(
        "abracadabra",
        new String[] { "cad", "abr" }
      )
    ); // Output: 5
    System.out.println(
      solution.findLengthOfLongestValidSubstring(
        "sunshine",
        new String[] { "sun", "shine" }
      )
    ); // Output: 6
    System.out.println(
      solution.findLengthOfLongestValidSubstring(
        "openai",
        new String[] { "pen", "ai" }
      )
    ); // Output: 3
  }
}

Complexity Analysis

Time Complexity:

The primary operations of this algorithm involve iterating over all possible substrings of the input string word, which is of length n. For each substring, the algorithm checks if it contains any of the forbidden substrings. This check involves iterating through each forbidden substring that can, in the worst case, take time for each check. Since the process of generating all substrings is , and checking each substring against all forbidden substrings can take up to time, the overall worst-case time complexity is .

Space Complexity:

The space complexity is constant because the algorithm uses a fixed amount of extra space regardless of the input size.