Post

3267 Find Longest Special Substring That Occurs Thrice I

Posted Updated
By Anurag
2 min read
3267 Find Longest Special Substring That Occurs Thrice I

Find Longest Special Substring That Occurs Thrice I image

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:

1
2
3
4
5
6

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

Example 2:

1
2
3
4
5

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

Example 3:

1
2
3
4
5
6

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

 

Constraints:

1
2

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


class Solution:
    def maximumLength(self, s: str) -> int:
        freq = [0] * 26
        for k in s:
            freq[ord(k) - 97] += 1
        #print(freq)
        

        @cache
        def find_occur(s1, s2):
            #print(s1, s2)
            for k in s1:
                if k != s1[0]:
                    return 0
            i = 0
            j = 0
            res = 0
            while(i < len(s2)):
                if s2[i] == s1[j]:
                    t1 = i
                    t2 = j
                    while(t1 < len(s2) and t2 < len(s1) and s2[t1] == s1[t2]):
                        t1 += 1
                        t2 += 1
                    if t2 == len(s1):
                        res += 1
                    i += 1
                    j = 0
                else:
                    i += 1
            return res


        i = 0
        ans = -1
        temp = 0
        while(i < len(s)):
            if freq[ord(s[i])-97] >= 3:
                j = i + 1
                while(j <= len(s)):
                    if find_occur(s[i:j], s) >= 3:
                        #print(s[i:j], j - i)
                        temp = j - i
                        j += 1
                    else:
                        break
                if temp > 0:
                    ans = max(ans, temp)
            else:
                if temp > 0:
                    ans = max(ans, temp)
                temp = 0
            i += 1
        return ans 

    #aaaa
leetcode
python
This post is licensed under CC BY 4.0 by the author.