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.
  1. Special String Again
  2. Discussions

Special String Again

Sort 736 Discussions, By:

  • ayushr2
     + 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

  • liquifiedart
     + 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;
    }

  • s_lazarus
     + 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)

  • shesanmigz
     + 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;
}

  • jinwoocheon
     + 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
Load more conversations