Test results - Codility

Tasks Details

hard

1. CountPalindromicSlices

Count the palindromic subwords of given string.

Task Score

100%

Correctness

100%

Performance

100%

In this problem we consider only strings consisting of lower-case English letters (a−z).

A string is a palindrome if it reads exactly the same from left to right as it does from right to left. For example, these strings are palindromes:

aza

abba

abacaba

These strings are not palindromes:

zaza

abcd

abacada

Given a string S of length N, a slice of S is a substring of S specified by a pair of integers (p, q), such that 0 ≤ p < q < N. A slice (p, q) of string S is palindromic if the string consisting of letters S[p], S[p+1], ..., S[q] is a palindrome. For example, in a string S = abbacada:

slice (0, 3) is palindromic because abba is a palindrome,

slice (6, 7) is not palindromic because da is not a palindrome,

slice (2, 5) is not palindromic because baca is not a palindrome,

slice (1, 2) is palindromic because bb is a palindrome.

Write a function

int solution(string &S);

that, given a string S of length N letters, returns the number of palindromic slices of S. The function should return −1 if this number is greater than 1,000,000,000.

For example, for string S = baababa the function should return 6, because exactly six of its slices are palindromic; namely: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..200,000];

string S is made only of lowercase letters (a−z).

Solution

Programming language used C++

Time spent on task 21 minutes

Notes

not defined yet

Code: 01:44:23 UTC, cpp, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

// you can use includes, for example:
// #include <algorithm>
#include <vector>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++11
    int count = 0;

	if(S.size() > 0)
	{
		std::string tempString = "#";

		for(int i = 0 ; i < S.size(); i++)
		{

			tempString.append(std::string(1,S[i]));
			tempString.append("#");
		}

		vector<int> palinCount(tempString.size());
		int C = 0, R = 0;

		for(int i = 1 ; i < tempString.size() - 1 ; i++)
		{
			int i_mirror = C - (i - C);

			palinCount[i] = (R > i) ? std::min(R-i, palinCount[i_mirror]) : 0;

			// Attempt to expand palindrome centered at i
			while((i + 1 + palinCount[i] < tempString.size() - 1 && i - 1 - palinCount[i] > 0) && (tempString[i + 1 + palinCount[i]] == tempString[i - 1 - palinCount[i]]))
				palinCount[i]++;

			count += palinCount[i]/2;

			if(count > 100000000)
				count = -1;


			// If palindrome centered at i expand past R,
			// adjust center based on expanded palindrome.
			if (i + palinCount[i] > R) {
				C = i;
				R = i + palinCount[i];
			}

		}
	}

	return count;
}

Analysis

expand all Example tests

▶

example
example

✘

WRONG ANSWER
got 5 expected 6

0.009 s

WRONG ANSWER, got 5 expected 6

Code: 01:46:05 UTC, java, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
         //This is where result will be stored
        int palindromicSlicesCount = 0;

        //Sanity check
        if (!String.IsNullOrEmpty(S))
        {
            //In order to be able to handle palindromes of odd and even lengths in the same way, we insert special character (#) between letters as well as delimiters.
            //i.g. 'baababa' becomes '^#b#a#a#b#a#b#a#$'
            S = "^#" + String.Join("#", Array.ConvertAll(S.ToCharArray(), c => c.ToString())) + "#$";
            int N = S.Length;

            //This is where the length of the longest palindrome centered at given index will be stored
            int[] P = new int[N];
            //This is where the index of current palindrome center will be stored
            int C = 0;
            //This is where the index of right edge of the palindrome most to the right will be stored
            int R = 0;

            //For every character index in the string
            for (int i = 1; i < N - 1; i++)
            {
                //We need to find the mirrored index i’ around the palindrome’s center C
                int iprime = C - (i - C);

                //If the palindrome most to the right reaches further then current index
                if (R > i)
                    //The initial palindrome length is calculated as minimum of 'distance between current index and the index of right edge of the palindrome most to the right' and 'the lenght of the longest palindrome centered at i’'
                    P[i] = Math.Min(R-i, P[iprime]);
                else
                    P[i] = 0;

                //Now we try to expand palindrome beyond the initial length
                while (S[i + 1 + P[i]] == S[i - 1 - P[i]])
                    P[i]++;

                //We can get the count of plaindormes around current index by dividing the lenght of the longest one by 2 (fixed point division)
                palindromicSlicesCount += P[i]/2;
                //If the number of palindromic slices is above 100,000,000 we should return -1
                if (palindromicSlicesCount > 100000000)
                {
                    palindromicSlicesCount = -1;
                    break;
                }

                //If the palindrome expands beyond R
                if (i + P[i] > R)
                {
                    //We need to adjust C and R
                    C = i;
                    R = i + P[i];
                }
            }
        }

        //Return the result
        return palindromicSlicesCount;
    }
}

Analysis

Compile error

Solution.java:17: error: illegal start of expression
            S = "^#" + String.Join("#", Array.ConvertAll(S.ToCharArray(), c => c.ToString())) + "#$";
                                                                             ^
1 error

Code: 01:46:27 UTC, cs, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");

class Solution {
    public int solution(string S) {
        //This is where result will be stored
        int palindromicSlicesCount = 0;

        //Sanity check
        if (!String.IsNullOrEmpty(S))
        {
            //In order to be able to handle palindromes of odd and even lengths in the same way, we insert special character (#) between letters as well as delimiters.
            //i.g. 'baababa' becomes '^#b#a#a#b#a#b#a#$'
            S = "^#" + String.Join("#", Array.ConvertAll(S.ToCharArray(), c => c.ToString())) + "#$";
            int N = S.Length;

            //This is where the length of the longest palindrome centered at given index will be stored
            int[] P = new int[N];
            //This is where the index of current palindrome center will be stored
            int C = 0;
            //This is where the index of right edge of the palindrome most to the right will be stored
            int R = 0;

            //For every character index in the string
            for (int i = 1; i < N - 1; i++)
            {
                //We need to find the mirrored index i’ around the palindrome’s center C
                int iprime = C - (i - C);

                //If the palindrome most to the right reaches further then current index
                if (R > i)
                    //The initial palindrome length is calculated as minimum of 'distance between current index and the index of right edge of the palindrome most to the right' and 'the lenght of the longest palindrome centered at i’'
                    P[i] = Math.Min(R-i, P[iprime]);
                else
                    P[i] = 0;

                //Now we try to expand palindrome beyond the initial length
                while (S[i + 1 + P[i]] == S[i - 1 - P[i]])
                    P[i]++;

                //We can get the count of plaindormes around current index by dividing the lenght of the longest one by 2 (fixed point division)
                palindromicSlicesCount += P[i]/2;
                //If the number of palindromic slices is above 100,000,000 we should return -1
                if (palindromicSlicesCount > 100000000)
                {
                    palindromicSlicesCount = -1;
                    break;
                }

                //If the palindrome expands beyond R
                if (i + P[i] > R)
                {
                    //We need to adjust C and R
                    C = i;
                    R = i + P[i];
                }
            }
        }

        //Return the result
        return palindromicSlicesCount;
    }
}

Analysis

expand all Example tests

▶

example
example

✔

0.062 s

Code: 01:48:02 UTC, cpp, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

// you can use includes, for example:
// #include <algorithm>
#include <vector>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++11
    int count = 0;

	if(S.size() > 0)
	{
		std::string tempString = "#";

		for(int i = 0 ; i < S.size(); i++)
		{

			tempString.append(std::string(1,S[i]));
			tempString.append("#");
		}

		vector<int> palinCount(tempString.size());
		int C = 0, R = 0;

		for(int i = 1 ; i < tempString.size() - 1 ; i++)
		{
			int i_mirror = C - (i - C);

			palinCount[i] = (R > i) ? std::min(R-i, palinCount[i_mirror]) : 0;

			// Attempt to expand palindrome centered at i
			while((i + 1 + palinCount[i] < tempString.size() - 1 && i - 1 - palinCount[i] > 0) && (tempString[i + 1 + palinCount[i]] == tempString[i - 1 - palinCount[i]]))
				palinCount[i]++;

			count += palinCount[i]/2;

			if(count > 100000000)
			{
				count = -1;
				break;

			}


			// If palindrome centered at i expand past R,
			// adjust center based on expanded palindrome.
			if (i + palinCount[i] > R) {
				C = i;
				R = i + palinCount[i];
			}

		}
	}

	return count;
}

Analysis

expand all Example tests

▶

example
example

✘

WRONG ANSWER
got 5 expected 6

0.009 s

WRONG ANSWER, got 5 expected 6

Code: 01:49:32 UTC, cpp, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

// you can use includes, for example:
// #include <algorithm>
#include <vector>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++11
    int count = 0;

	if(S.size() > 0)
	{
		std::string tempString = "#";

		for(int i = 0 ; i < S.size(); i++)
		{

			tempString.append(std::string(1,S[i]));
			tempString.append("#");
		}

		vector<int> palinCount(tempString.size());
		int C = 0, R = 0;

		for(int i = 1 ; i < tempString.size() - 1 ; i++)
		{
			int i_mirror = C - (i - C);

			palinCount[i] = (R > i) ? std::min(R-i, palinCount[i_mirror]) : 0;

			// Attempt to expand palindrome centered at i
			while((i + 1 + palinCount[i] < tempString.size() - 1 && i - 1 - palinCount[i] > 0) && (tempString[i + 1 + palinCount[i]] == tempString[i - 1 - palinCount[i]]))
				palinCount[i]++;

				if(tempString[i] == '#')
			{
				count += palinCount[i + 1]/2;
			}
			else
			{
				count += palinCount[i]/2;
			}

			if(count > 100000000)
			{
				count = -1;
				break;

			}


			// If palindrome centered at i expand past R,
			// adjust center based on expanded palindrome.
			if (i + palinCount[i] > R) {
				C = i;
				R = i + palinCount[i];
			}

		}
	}

	return count;
}

Analysis

expand all Example tests

▶

example
example

✘

WRONG ANSWER
got 4 expected 6

0.009 s

WRONG ANSWER, got 4 expected 6

Code: 01:50:33 UTC, cpp, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

// you can use includes, for example:
// #include <algorithm>
#include <vector>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++11
    int count = 0;

	if(S.size() > 0)
	{
		std::string tempString = "#";

		for(int i = 0 ; i < S.size(); i++)
		{

			tempString.append(std::string(1,S[i]));
			tempString.append("#");
		}

		vector<int> palinCount(tempString.size());
		int C = 0, R = 0;

		for(int i = 1 ; i < tempString.size() - 1 ; i++)
		{
			int i_mirror = C - (i - C);

			palinCount[i] = (R > i) ? std::min(R-i, palinCount[i_mirror]) : 0;

			// Attempt to expand palindrome centered at i
			while((i + 1 + palinCount[i] < tempString.size() - 1 && i - 1 - palinCount[i] > 0) && (tempString[i + 1 + palinCount[i]] == tempString[i - 1 - palinCount[i]]))
				palinCount[i]++;

				if(tempString[i] == '#')
			{
				count += (palinCount[i] + 1)/2;
			}
			else
			{
				count += palinCount[i]/2;
			}

			if(count > 100000000)
			{
				count = -1;
				break;

			}


			// If palindrome centered at i expand past R,
			// adjust center based on expanded palindrome.
			if (i + palinCount[i] > R) {
				C = i;
				R = i + palinCount[i];
			}

		}
	}

	return count;
}

Analysis

expand all Example tests

▶

example
example

✔

0.009 s

Code: 01:50:44 UTC, cpp, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

// you can use includes, for example:
// #include <algorithm>
#include <vector>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++11
    int count = 0;

	if(S.size() > 0)
	{
		std::string tempString = "#";

		for(int i = 0 ; i < S.size(); i++)
		{

			tempString.append(std::string(1,S[i]));
			tempString.append("#");
		}

		vector<int> palinCount(tempString.size());
		int C = 0, R = 0;

		for(int i = 1 ; i < tempString.size() - 1 ; i++)
		{
			int i_mirror = C - (i - C);

			palinCount[i] = (R > i) ? std::min(R-i, palinCount[i_mirror]) : 0;

			// Attempt to expand palindrome centered at i
			while((i + 1 + palinCount[i] < tempString.size() - 1 && i - 1 - palinCount[i] > 0) && (tempString[i + 1 + palinCount[i]] == tempString[i - 1 - palinCount[i]]))
				palinCount[i]++;

			if(tempString[i] == '#')
			{
				count += (palinCount[i] + 1)/2;
			}
			else
			{
				count += palinCount[i]/2;
			}

			if(count > 100000000)
			{
				count = -1;
				break;

			}


			// If palindrome centered at i expand past R,
			// adjust center based on expanded palindrome.
			if (i + palinCount[i] > R) {
				C = i;
				R = i + palinCount[i];
			}

		}
	}

	return count;
}

Analysis

expand all Example tests

▶

example
example

✔

0.009 s

Code: 01:50:48 UTC, cpp, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

// you can use includes, for example:
// #include <algorithm>
#include <vector>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(string &S) {
    // write your code in C++11
    int count = 0;

	if(S.size() > 0)
	{
		std::string tempString = "#";

		for(int i = 0 ; i < S.size(); i++)
		{

			tempString.append(std::string(1,S[i]));
			tempString.append("#");
		}

		vector<int> palinCount(tempString.size());
		int C = 0, R = 0;

		for(int i = 1 ; i < tempString.size() - 1 ; i++)
		{
			int i_mirror = C - (i - C);

			palinCount[i] = (R > i) ? std::min(R-i, palinCount[i_mirror]) : 0;

			// Attempt to expand palindrome centered at i
			while((i + 1 + palinCount[i] < tempString.size() - 1 && i - 1 - palinCount[i] > 0) && (tempString[i + 1 + palinCount[i]] == tempString[i - 1 - palinCount[i]]))
				palinCount[i]++;

			if(tempString[i] == '#')
			{
				count += (palinCount[i] + 1)/2;
			}
			else
			{
				count += palinCount[i]/2;
			}

			if(count > 100000000)
			{
				count = -1;
				break;

			}


			// If palindrome centered at i expand past R,
			// adjust center based on expanded palindrome.
			if (i + palinCount[i] > R) {
				C = i;
				R = i + palinCount[i];
			}

		}
	}

	return count;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example
example

✔

0.009 s

expand all Correctness tests

▶

simple1
S=caabbbaa

✔

0.009 s

▶

simple2
S=abababbbabbbaba

✔

0.009 s

▶

simple3
palindromic string

✔

0.009 s

▶

extreme_short
empty string, single character string

✔

0.009 s

▶

no_palindromes
no palindromic slices

✔

0.009 s

expand all Performance tests

▶

result_too_large
only a's, result over 100000000

✔

0.011 s

▶

medium2
chaotic (a,b)^500

✔

0.009 s

▶

large1
a*1000 + b*1000 + a*1000

✔

0.009 s

▶

large2
b*2000 + a*2000 + b*2000 + a*2000

✔

0.010 s

▶

large3
chaotic (a,b)^10000

✔

0.011 s

▶

large4
chaotic (a^200, b^200, c^200, d^200)^100

✔

0.011 s

▶

large5
b*10000 + a*10000

✔

0.012 s

▶

large6

✔

0.011 s

▶

large7
ab*10000

✔

0.012 s