2781. Length of the Longest Valid Substring

link

Dataset 10^5 10^5 could be in O(n) or O(n log n)

When see the string length = 10 , can bring up with k * n solution. (k = max string length)

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:

        n = len(word)

        f = set(forbidden)
        mx = max(list(len(f) for f in forbidden))

        def check(right):
            current = ''
            # care about the edge case
            for i in range(right, max(right-mx, left - 1, -1), -1):
                current = word[i] + current
                # print(current, left, right)
                if current in f:
                    return True

            return False

        left = 0
        res = 0
        for right in range(n):

            while check(right):
                left += 1

            res = max(res, right - left + 1)

        return res

Faster solution

Direct return i index as left

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:

        n = len(word)

        f = set(forbidden)
        mx = max(list(len(f) for f in forbidden))

        def check(right):
            current = ''
            # care about the edge case
            for i in range(right, max(right-mx, left - 1, -1), -1):
                current = word[i] + current
                if current in f:
                    return i

            return -1

        left = 0
        res = 0
        for right in range(n):

            r = check(right)

            if r != -1:
                left = r + 1

            res = max(res, right - left + 1)

        return res