Welcome to Subscribe On Youtube
2781. Length of the Longest Valid Substring
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.
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.
Solutions
-
class Solution { public int longestValidSubstring(String word, List<String> forbidden) { var s = new HashSet<>(forbidden); int ans = 0, n = word.length(); for (int i = 0, j = 0; j < n; ++j) { for (int k = j; k > Math.max(j - 10, i - 1); --k) { if (s.contains(word.substring(k, j + 1))) { i = k + 1; break; } } ans = Math.max(ans, j - i + 1); } return ans; } }
-
class Solution { public: int longestValidSubstring(string word, vector<string>& forbidden) { unordered_set<string> s(forbidden.begin(), forbidden.end()); int ans = 0, n = word.size(); for (int i = 0, j = 0; j < n; ++j) { for (int k = j; k > max(j - 10, i - 1); --k) { if (s.count(word.substr(k, j - k + 1))) { i = k + 1; break; } } ans = max(ans, j - i + 1); } return ans; } };
-
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
-
func longestValidSubstring(word string, forbidden []string) (ans int) { s := map[string]bool{} for _, x := range forbidden { s[x] = true } n := len(word) for i, j := 0, 0; j < n; j++ { for k := j; k > max(j-10, i-1); k-- { if s[word[k:j+1]] { i = k + 1 break } } ans = max(ans, j-i+1) } return } func max(a, b int) int { if a > b { return a } return b }
-
function longestValidSubstring(word: string, forbidden: string[]): number { const s: Set<string> = new Set(forbidden); const n = word.length; let ans = 0; for (let i = 0, j = 0; j < n; ++j) { for (let k = j; k > Math.max(j - 10, i - 1); --k) { if (s.has(word.substring(k, j + 1))) { i = k + 1; break; } } ans = Math.max(ans, j - i + 1); } return ans; }