Re: [閒聊] 每日leetcode
2981. Find Longest Special Substring That Occurs Thrice I
## 思路
hash table記錄 連續同字元長度的個數
aaabbaa -> a3=1, b2=1, a2=1
然後對每個字元檢查幾個Case:
1. max_len個數>=3 (aaa b aaa b aaa)
=> 可以組出三組aaa (max_len)
2. max_len個數==2 (aaa b aaa)
3. max_len個數==1, 且有max_len-1 (aaa b aa)
=> 可以組出三組aa (max_len-1)
4. max_len>2 (aaa b)
=> 可以組出三組a (max_len-2)
## Code
```python
class Solution:
def maximumLength(self, s: str) -> int:
n = len(s)
counter = defaultdict(Counter)
size = 1
for i in range(1, n):
if s[i] != s[i-1]:
counter[s[i-1]][size] += 1
size = 0
size += 1
counter[s[-1]][size] += 1
res = -1
for counts in counter.values():
max_len = max(counts)
# aaa b aaa b aaa c aaa -> 3
if counts[max_len] >= 3:
res = max(res, max_len)
# aaa b aaa -> 2
elif counts[max_len] == 2:
res = max(res, max_len-1)
# aaa b aa -> 2
elif counts[max_len] == 1 and counts[max_len-1]:
res = max(res, max_len-1)
# aaa b -> 1
elif max_len > 2:
res = max(res, max_len-2)
return res if res else -1
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.205.147 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733830601.A.01A.html
推
12/10 19:40,
1年前
, 1F
12/10 19:40, 1F
→
12/10 19:56,
1年前
, 2F
12/10 19:56, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1192 之 1554 篇)：