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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Special String Again
  2. Discussions

Special String Again

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 765 Discussions, By:

recency

Please Login in order to post a comment

  • matous_work
    1 week ago+ 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|
    Permalink
  • tomek_juszczysz1
    3 weeks ago+ 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|
    Permalink
  • nleo575
    1 month ago+ 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
    
    0|
    Permalink
  • agent_matrix_bo1
    1 month ago+ 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|
    Permalink
  • prsephton
    1 month ago+ 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
    
    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy