hopefully a readable one:
long substrCount(int n, string s) {
// minimum count is n int count = n; for (int i=0;i<n;i++) { char current = s[i]; // just continuous - equal substrings like "aaa" int j = i+1; while (j<n && s[j] == current) { count++; j++; } // continuous on left and right side from current char j = 1; while (i-j>=0 && i+j<n && // array bounds current != s[i+j] && // next is different than current s[i-j] == s[i+j] && // char's on left and right sides are the same s[i+j] == s[i+1] // next char must be the same as previous ) { count++; j++; } } return count;}
def substrCount(n, s): current_char = s[0] occurences = [[current_char,0]] # first we create a list of all occurences of letters, but we count repetitions, like for "aabaa" we would have [["a",2],["b",1],["a",2]] for char in s: if char == current_char: occurences[-1][1] +=1 else: occurences.append([char,1]) current_char = char # now we calculate specials that are from <one char> substrings - the amount is equal to (x^2+x)/2 if the length is x specials = sum([(occurence[1]**2 + occurence[1]) / 2 for occurence in occurences]) # now we add the cases where there is a different char in the middle for i in range(1,len(occurences)-1): if (occurences[i][1] == 1) and (occurences[i-1][0] == occurences[i+1][0]): specials += min(occurences[i-1][1],occurences[i+1][1]) return int(specials)
Python 3 solution with single pass of string. Time: O(n). Space: O(1). Managed to avoid all but outer loop.
def substrCount(n, s): char = s[0] # Previous character to compare against count = n # Count of special substrings in s, min(count) is n diff_mid = False # Flag indicating when in condition 2 ic2 = None # Index where condition 2 starts seq = 1 # Length of current repeating sequence seq_p = 0 # Length of previous repeating sequence before condition 2 n1 = n - 1 for i in range(1, n): # Condition 1: check if s[i] is continuing a repeating sequence if s[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 applies if diff_mid: if seq < seq_p: count += 1 else: # Otherwise exit condition 2 diff_mid = False else: # Check if in condition 2 if i == ic2: count += 1 else: diff_mid = False # Check if about to enter condition 2 if i < n1 and char == s[i + 1]: seq_p = seq + 1 # Add 1 to avoid having to do <= comparison diff_mid = True ic2 = i + 1 seq = 1 char = s[i] return count
String input = "abcbaba";
My answer is 11 but the expected answer is 10.
a,b,c,b,a,b,a,abcba,bcb,bab,aba - total of 11.
Can someone explain to me if my expectation is wrong?
The naive solution never seems to be good enough here. Identifying each substring and testing if its valid ends up having a loop within a loop, and timing out.
Nope, HackerRank wants a single traversal over the string and some clever hacks.
def substrCount(n, s): nsubs, nchars, ch = 1, 1, s[0] for i in range(1,n): if ch == s[i]: nchars += 1 nsubs += nchars else: for j in range(i+1, min(n, i+1+nchars)): if s[j] != ch: break; nsubs += 1 ch, nchars = s[i], 1 nsubs += 1 return nsubs
Load more conversations
Sort 765 Discussions, By:
Please Login in order to post a comment