Daily Leetcode Challenge | DEC 10 | PART-2 | Longest Special Substring That Occurs Thrice I

[@darshankumar5546]

# best possible -- optimal solution
# n=10^5
#time complexity: O(n+26.n)=O(n)
# space complexity: O(26.n)=O(n)
class Solution:
def maximumLength(self, s: str) -> int:
n=len(s)
spl_subStringLen=1
a={chr(i):[0 for _ in range(n)] for i in range(ord('a'),ord('z')+1)}
#print(f"initially:
",a)
a[s[0]][0]=1
for i in range(1,n):
if(s[i]==s[i-1]):
spl_subStringLen+=1
else:
spl_subStringLen=1
a[s[i]][spl_subStringLen-1]+=1
#print(f"after populating spl ss freq:
",a)
ans=-1
for asciii in range(ord('a'),ord('z')+1):
char=chr(asciii)
i=n-1
while(i>=0 and a[char][i]==0):
i-=1
ans=max(ans,i+1 if a[char][i]>=3 else -1)
if(i-1>=0):
a[char][i-1]+=a[char][i]
ans=max(ans,(i-1)+1 if a[char][i-1]>=3 else -1)
if(i-2>=0):
a[char][i-2]+=a[char][i-1]
ans=max(ans,(i-2)+1 if a[char][i-2]>=3 else -1)
#print(f"finally:
",a)
return ans
# 'a': [0, 0, 0, 0] # step 1
# 'a': [1, 1, 1, 1] # step 2
# 'a': [1, 3, 2, 1] # step 3

[@darshankumar5546]

Part -1 video: th-cam.com/video/30bbrywYz6s/w-d-xo.html