Algorithm help is needed (Codility) [duplicate]

Question

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(const 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 100,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).

Assume that:
- N is an integer within the range [0..20,000];
- string S consists only of lower-case letters (a−z).

Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Here is my solution:

int palindrom(const string &S, int startIndex,int endIndex, int counter=0)
{ 
    bool equals = true;
    if (endIndex - startIndex < 1)
        return counter;
    for(int i = startIndex,j = endIndex;i<j; ++i, --j)
    {
        equals = S[i] == S[j];
        if (!equals) break;
    }
    if (equals) counter++;
    counter = palindrom( S,startIndex,endIndex-1,counter);
    return counter;
}

int solution(const string &S)
{
    int length = S.size();
    int counter = 0;
    if (length > 20000) return -1;
    for(int i=0; i < length-1; i++)
    {
        counter += palindrom(S,i,length-1);
        if (counter > 100000000) return -1;
    }
    return counter;
}

with big strings S.size()>3000 I always get runtime error(means time is more then 3 sec but solution should work in less then 2 seconds)! Any suggestions?

ok! and main function is something like:

main(){cout<<solution("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");}

Answer 1

I would do without recursion

#include <string>
#include <iostream>

typedef std::string::const_iterator P;

bool is_palindrom(P begin, P end) {
    while (begin < end) {
        if (*begin != *end)
            return false;
        ++begin;
        --end;
    }
    return true;
}

int count_palindroms(const std::string &s) {
    int c = 0;
    P left = s.begin();
    while (left < s.end()) {
        P right = left + 1; // because length palindrome > 1
        while (right < s.end()) {
            if (is_palindrom(left, right)) {
                //std::cout << left - s.begin() << ' ' << right - s.begin() << std::endl;
                c++;
                if (c > 100000000)
                    return -1;
            }
            ++right;
        }
        ++left;
    }
    return c;
}

int main(int , char *[])
{
    std::cout << count_palindroms("baababa") << std::endl;
    return 0;
}

Answer 2

It works fine on my PC. What you are actually doing here is checking every sub string of the original string and run a recursive function over it. As @PeterT mentioned you probably reach the max depth of your stuck.

What I would do is not use the call stack, but either use my own stuck, or use some simple string functions like:

std::string s = "aba";
std::string s1 = std::string(s.rbegin(), s.rend()); 
if (s == s1)
{
///...
}

for an example.

Regarding the time complexity - as you can read here you can't check them all in o(n).