Leetcode 2781. 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.

단어와 금지된 문자열들이 주어진다.
단어의 부분 문자열은 안에 금지된 문자열을 포함하지 않아야 한다.
조건을 만족하는 가장 긴 부분 문자열의 길이를 구하시오.

예시

Input: word = "cbaaaabc", forbidden = ["aaa","cb"]
Output: 4
Explanation: aabc 가 aaa와 cb를 포함하지 않으면서 가장 길다.
고로 답은 aabc의 길이인 4가 된다.

제한

• $1 <= word.length <= 10^5$
• 단어는 반드시 소문자만을 포함한다.
• $1 <= forbidden.length <= 10^5$
• $1 <= forbidden[i].length <= 10$
• 금지 문자열은 반드시 소문자만을 포함한다.

풀이법

POINT 1, 금지된 문자열의 길이는 10개를 넘지 않는다.

• 문자열을 체크할때 10개 이상은 체크할 필요가 없다.

POINT 2, 금지된 문자열은 set을 통해 O(1) 시간 복잡도로 확인할수 있다.

---

이를 이용한 풀이

EX. cbaaaabc 와 ['aaa', 'bc']

1. 먼저 맨 오른쪽의 c만 확인한다.
   • c는 금지된 문자열에 미포함! 최대 길이는 1로 갱신한다.
2. 그 후 b와 bc를 검사한다.
   • bc까지 검사했는데 금지된 문자열에 미포함하기에 bc의 길이인 2로 갱신한다.
3. a, ab, abc 를 검사한다.
   • 3으로 최대길이를 갱신한다.
4. a, aa, aab, aabc 를 검사한다.
   • 4로 최대길이를 갱신한다.
5. a, aa, aaa ( 금지된 문자열 포함 ) 를 검사한다.
   • aaa는 금지된 문자열이 포함된다! 이 경우 aa 이후에 나오는 모든 문자열은
     반드시 금지된 문자열을 포함한다는 의미를 가진다.
   • 검사하는 문자열의 오른쪽 끝 최대길이를 aa의 마지막 문자부분으로 제한한다.
6. a, aa, aaa
   • 반복..

POINT

• 여기서 검사하는 문자열의 길이는 10개를 넘지 않도록 min연산자를 활용하는것이 포인트!

코드

class Solution:
    def longestValidSubstring(self, word: str, forbidden: List[str]) -> int:
    	# 문자열 검사하는것의 끝부분
        right = len(word)
        # 갱신할 최대길이
        ans = 0

		# 금지 문자열 모음 
        f = set(forbidden)

		# 왼쪽은 하나하나씩 옮긴다.
        for left in range(len(word) - 1, -1, -1):
        	# 검사할 문자열들
            # 반드시 길이가 10을 넘지 않는다.
            for i in range(left + 1, min(right + 1, left + 11)):
                # 검사할 대상 문자열
                w = word[left:i]
                # 만약 금지대상에 포함시 오른쪽 끝을 옮기고 여기서 멈춤!
                if w in f:
                    right = i - 1
                    break
            # 찾은 최대 길이로 갱신.
            ans = max(ans, right - left)

        return ans

814ms 가 최선인걸 보면 애초에 엄청 빠른 알고리즘이 존재하는 문제는 아닌듯..