Leetcode Problem 2781. Length of the Longest Valid Substring

2781. Length of the Longest Valid Substring

Leetcode Solutions

Greedy Two Pointers Approach

  1. Initialize an array v of length n (the length of word) with all elements set to n.
  2. Create a hashmap mp to store the forbidden substrings.
  3. Iterate over each index i of word: a. Create a temporary string s. b. For each index j from i to n and while j-i is less than 10: i. Append word[j] to s. ii. If s is in mp, set v[i] to j and break.
  4. Initialize ans to store the maximum valid substring length and curr to store the current valid substring length.
  5. Use two pointers i and j to iterate over word: a. If v[i] is n, increment curr. b. Otherwise, find the minimum index idx such that v[j] is less than n and update curr and ans accordingly. c. Reset curr if a forbidden substring is encountered.
  6. Return ans as the length of the longest valid substring.
UML Thumbnail

Trie-based Substring Search

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...