We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Python 3 solution with single pass of string. Time: O(n). Space: O(1).
Managed to avoid all but outer loop.
defsubstrCount(n,s):char=s[0]# Previous character to compare againstcount=n# Count of special substrings in s, min(count) is ndiff_mid=False# Flag indicating when in condition 2ic2=None# Index where condition 2 startsseq=1# Length of current repeating sequenceseq_p=0# Length of previous repeating sequence before condition 2n1=n-1foriinrange(1,n):# Condition 1: check if s[i] is continuing a repeating sequenceifs[i]==char:count+=seq# Need to account for all substrings of length k | k in [2, seq]seq+=1# Check if condition 2 exists, and still appliesifdiff_mid:ifseq<seq_p:count+=1else:# Otherwise exit condition 2diff_mid=Falseelse:# Check if in condition 2ifi==ic2:count+=1else:diff_mid=False# Check if about to enter condition 2ifi<n1andchar==s[i+1]:seq_p=seq+1# Add 1 to avoid having to do <= comparisondiff_mid=Trueic2=i+1seq=1char=s[i]returncount
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Special String Again
You are viewing a single comment's thread. Return to all comments →
Python 3 solution with single pass of string. Time: O(n). Space: O(1). Managed to avoid all but outer loop.