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 736 Discussions, By:

votes

Please Login in order to post a comment

  • ayushr2
    4 years ago+ 61 comments

    Really simple 3 pass solution: 1. Build a list of tuples such that the string "aaabbc" can be squashed down to [("a", 3), ("b", 2), ("c", 1)]. 2. add to answer all combinations of substrings from these tuples which would represent palindromes which have all same letters. 3. traverse this list to specifically find the second case mentioned in probelm

    Here is my code:

    def substrCount(n, s):
        l = []
        count = 0
        cur = None
    
    # 1st pass
        for i in range(n):
            if s[i] == cur:
                count += 1
            else:
                if cur is not None:
                    l.append((cur, count))
                cur = s[i]
                count = 1
        l.append((cur, count))
    
        ans = 0
    		
    # 2nd pass
        for i in l:
            ans += (i[1] * (i[1] + 1)) // 2
    
    # 3rd pass
        for i in range(1, len(l) - 1):
            if l[i - 1][0] == l[i + 1][0] and l[i][1] == 1:
                ans += min(l[i - 1][1], l[i + 1][1])
    
        return ans
    
    240|
    Permalink
    View more Comments..
  • liquifiedart
    4 years ago+ 15 comments

    The hardest part, was getting my brain to refocus on this "Special Palindrone" definition. Originally I was coding for a normal palindrone, which is VASTLY different and more complicated. Once I wasted time on that and re-read the problem, the solution wasn't too difficult.

    My Solution: C#

        static long substrCount(string s)
        {
            long retVal = s.Length;
    
            for (int i = 0; i < s.Length; i++)
            {
                var startChar = s[i];
                int diffCharIdx = -1;
                for (int j = i + 1; j < s.Length; j++)
                {
                    var currChar = s[j];
                    if (startChar == currChar)
                    {
                        if ((diffCharIdx == -1) ||
                           (j - diffCharIdx) == (diffCharIdx - i))
                            retVal++;
                    }
                    else
                    {
                        if (diffCharIdx == -1)
                            diffCharIdx = j;
                        else
                            break;
                    }
                }
            }
            return retVal;
        }
    
    76|
    Permalink
    View more Comments..
  • s_lazarus
    3 years ago+ 1 comment

    The testcases for this are very disappointing. There's only 3 test cases that are human-parsable. There should be more than this.

    The custom testcase I used that found the error I had in my code despite passing the 3 human-parsable test cases:

    7 aaabaaa

    (should be 16)

    52|
    Permalink
  • shesanmigz
    4 years ago+ 3 comments

    Java 8

    Passed all test cases

    static long substrCount(int n, String s) {
        // initialize counter to n because each character is a
        // palindromic string
        int counter = n;
    				
        // to count consecutive characters that are the same
        int consec = 1;
    				
        // the middle index of a 3-character symmetry,
        // assigned only once detected
        int midIndex = -1;
    				
        // compare with previous character so start with i=1
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i-1)) {
                // Condition 1: All of the characters are the same
                // For n consecutive characters that are the same,
                // we have this formula:
                // Number of palindromic strings =
                //     (n-1) + (n-2) + ... + (n-(n-1))
                counter += consec;
                consec++;
                    
                // Condition 2: All characters except the middle one
                // are the same
                if (midIndex > 0) {
                    // check for symmetry on both sides
                    // of the midIndex
                    if ((midIndex-consec) > 0 && s.charAt(midIndex-consec) == s.charAt(i)) {
                        counter++;
                    } else {
                        // no more possibility of palindromic string
                        // with this midIndex
                        midIndex = -1; 
                    }
                }
            } else {
                // reset consecutive chars counter to 1
                consec = 1;
                    
                // check for a 3-character symmetry
                if (((i-2) >= 0) && s.charAt(i-2) == s.charAt(i)) {
                    counter++; // 3-char symmetry is detected
                        
                    // to check if the next characters are the same
                    // and symmetrical along the midIndex
                    midIndex = i-1;
                } else {
                    midIndex = -1;
                }
            }
        }
        return counter;
    }
    
    34|
    Permalink
  • jinwoocheon
    3 years ago+ 8 comments

    Here's a really simple solution for Python3:

    def substrCount(n, s):
        count = n
        for x in range(n): 
            y = x
            while y < n - 1:
                y += 1
                if s[x] == s[y]:
                    count += 1
                else:
                    if s[x:y] == s[y+1:2*y-x+1]:
                        count += 1
                    break
    
        return count
    
    22|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature