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.
- Special String Again
- Discussions
Special String Again
Special String Again
+ 0 comments 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;
}
+ 0 comments 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)
+ 0 comments 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
+ 1 comment 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?
+ 0 comments 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