[LeetCode] 2981. Find Longest Special Substring That Occurs Thrice I (Python)

 

난이도: Medium

문제 설명

---

You are given a string s that consists of lowercase English letters.

A string is called special if it is made up of only a single character. For example, the string "abc" is not special, whereas the strings "ddd", "zz", and "f" are special.

Return the length of the longest special substring of s which occurs at least thrice, or -1 if no special substring occurs at least thrice.

A substring is a contiguous non-empty sequence of characters within a string.

 

문제 예제

---

Example 1:

Input: s = "aaaa"
Output: 2
Explanation: The longest special substring which occurs thrice is "aa":
substrings "aaaa", "aaaa", and "aaaa".
It can be shown that the maximum length achievable is 2.

 

Example 2:

Input: s = "abcdef"
Output: -1
Explanation: There exists no special substring which occurs at least thrice.
Hence return -1.

 

Example 3:

Input: s = "abcaba"
Output: 1
Explanation: The longest special substring which occurs thrice is "a":
substrings "abcaba", "abcaba", and "abcaba".
It can be shown that the maximum length achievable is 1.

 

제한 사항

---

• 3 <= s.length <= 50
• s consists of only lowercase English letters.

 

✏️ Solution(솔루션)

---

class Solution:
    def maximumLength(self, s: str) -> int:
        substring_dic = defaultdict(int)
        n = len(s)

        for i in range(n):
            j = i+1
            substring_dic[s[i]] += 1
            temp = s[i]

            while True:
                if j == n or s[i] != s[j]:
                    break
                temp += s[j]
                substring_dic[temp] += 1
                j+=1
                
        answer = -1

        for substring in substring_dic:
            if substring_dic[substring] >= 3:
                answer = max(answer, len(substring))
        
        return answer

 

s의 요소를 하나씩 확인하면서 substring_dic의 각 요소의 갯수를 저장했다.

또, 한 요소를 확인할 때, 그 다음 요소도 현재 요소와 같을 때까지 확인하고 각 substring에 대한 갯수도 substring_dic에 저장했다.

 

예를들어, "aaabb"가 input으로 주어졌을 때, 먼저 a라는 요소를 +1 해준다. 그후, 그 다음요소도 a이기 때문에 aa도 +1 해준다. 그 다음 역시 a 이기 때문에 aaa도 +1해준다. 그다음은 b라서 다음 요소로 넘어간다.

 

모든 요소별로 위와 같은 작업을 반복했다.

 

모든 요소를 확인하고 나서는 substring_dic에서 3개 이상 저장된 substring을 확인하고 제일 긴 길이를 반환하여 정답을 맞출 수 있었다.

---

[LeetCode] 2981. Find Longest Special Substring That Occurs Thrice I