2781. Length of the Longest Valid Substring LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2781. Length of the Longest Valid Substring LeetCode Solution with the best time and space complexity. The solution to Length of the Longest Valid Substring problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Length of the Longest Valid Substring solution in C++
Length of the Longest Valid Substring solution in Java
Length of the Longest Valid Substring solution in Python
Additional Resources

2781. Length of the Longest Valid Substring LeetCode Solution image

Problem Statement of Length of the Longest Valid Substring

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.

Example 1:

Input: word = “cbaaaabc”, forbidden = [“aaa”,”cb”]
Output: 4
Explanation: 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
Explanation: 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.

Complexity Analysis

Time Complexity: O(100n) = O(n)
Space Complexity: O(|\texttt{forbidden})

2781. Length of the Longest Valid Substring LeetCode Solution in C++

class Solution {
 public:
  int longestValidSubstring(string word, vector<string>& forbidden) {
    int ans = 0;
    unordered_set<string> forbiddenSet{forbidden.begin(), forbidden.end()};

    // r is the rightmost index to make word[l..r] a valid substring.
    int r = word.length() - 1;
    for (int l = word.length() - 1; l >= 0; --l) {
      for (int end = l; end < min(l + 10, r + 1); ++end)
        if (forbiddenSet.contains(word.substr(l, end - l + 1))) {
          r = end - 1;
          break;
        }
      ans = max(ans, r - l + 1);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

2781. Length of the Longest Valid Substring LeetCode Solution in Java

class Solution {
  public int longestValidSubstring(String word, List<String> forbidden) {
    int ans = 0;
    Set<String> forbiddenSet = new HashSet<>(forbidden);

    // r is the rightmost index to make word[l..r] a valid substring.
    int r = word.length() - 1;
    for (int l = word.length() - 1; l >= 0; --l) {
      for (int end = l; end < Math.min(l + 10, r + 1); ++end)
        if (forbiddenSet.contains(word.substring(l, end + 1))) {
          r = end - 1;
          break;
        }
      ans = Math.max(ans, r - l + 1);
    }

    return ans;
  }
}
// code provided by PROGIEZ

2781. Length of the Longest Valid Substring LeetCode Solution in Python

class Solution:
  def longestValidSubstring(self, word: str, forbidden: list[str]) -> int:
    forbiddenSet = set(forbidden)
    ans = 0
    r = len(word) - 1  # rightmost index of the valid substring

    for l in range(len(word) - 1, -1, -1):
      for end in range(l, min(l + 10, r + 1)):
        if word[l:end + 1] in forbiddenSet:
          r = end - 1
          break
      ans = max(ans, r - l + 1)

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents