5

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");}
Improve this question
17
  • 5
    Format your code so we can read it without scrolling. Include the error so we can make an informed guess. What platform are you running on? What compiler are you using? Commented Jul 28, 2013 at 13:58
  • 2
    Don't miss the Formatting Help, it's badly needed on a question like this. People will be more willing to do work for you if you make it easy on them. Commented Jul 28, 2013 at 14:00
  • 3
    The down votes are pointless. Give him a chance to improve the question. This looks like an interesting one. Commented Jul 28, 2013 at 14:00
  • 2
    @devworkstation You have to use the edit link, you can't submit a new question that is exactly the same as this one. Otherwise I'm not sure what problems you're running into. Jrok already formatted the big code block, but you should be able to add line breaks to create paragraphs and surround inline code blocks with backticks (``) Commented Jul 28, 2013 at 14:03
  • 1
    Can you post main() and your input text? Commented Jul 28, 2013 at 14:04

3 Answers 3

Reset to default
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;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for the reply! As for me - my solution looks more readable. But anyway your solution is still very slow.
1

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).

Improve this answer

1 Comment

He does not want to print all strings, only to count them. This might invalidate the proof of O(n^2). Although admittedly, I also think this can't be done in O(n).
0

I would simply delete the recursion (with a small change in the algorithm):

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

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.