title: Algorithm help is needed (Codility)
body: <p>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.</p>
  
  <p>For example, these strings are palindromes:</p>
  
  <pre><code>aza
  abba
  abacaba
  </code></pre>
  
  <p>These strings are not palindromes:</p>
  
  <pre><code>zaza
  abcd
  abacada
  </code></pre>
  
  <p>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 <code>0 ≤ p &lt; q &lt; N</code>. A slice (p, q) of string S is palindromic if the string consisting of letters <code>S[p], S[p+1], ..., S[q]</code> is a palindrome.</p>
  
  <p>For example, in a string <code>S = abbacada:</code></p>
  
  <p>slice (0, 3) is palindromic because <code>abba</code> is a palindrome,<br>
  slice (6, 7) is not palindromic because <code>da</code> is not a palindrome,<br>
  slice (2, 5) is not palindromic because <code>baca</code> is not a palindrome,<br>
  slice (1, 2) is palindromic because <code>bb</code> is a palindrome.  </p>
  
  <hr>
  
  <p>Write a function <code>int solution(const string &amp;S);</code> 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.</p>
  
  <p>For example, for string <code>S = baababa</code> the function should return 6, because exactly six of its slices are palindromic; namely: <code>(0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6)</code>.</p>
  
  <p>Assume that:<br>
  - N is an integer within the range [0..20,000];<br>
  - string S consists only of lower-case letters (a−z).  </p>
  
  <p>Complexity:<br>
  - expected worst-case time complexity is O(N);<br>
  - expected worst-case space complexity is O(N) (not counting the storage required for input arguments).  </p>
  
  <p>Here is my solution:</p>
  
  <pre><code>int palindrom(const string &amp;S, int startIndex,int endIndex, int counter=0)
  { 
      bool equals = true;
      if (endIndex - startIndex &lt; 1)
          return counter;
      for(int i = startIndex,j = endIndex;i&lt;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 &amp;S)
  {
      int length = S.size();
      int counter = 0;
      if (length &gt; 20000) return -1;
      for(int i=0; i &lt; length-1; i++)
      {
          counter += palindrom(S,i,length-1);
          if (counter &gt; 100000000) return -1;
      }
      return counter;
  }
  </code></pre>
  
  <p>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?</p>
  
  <p>ok! and main function is something like:</p>
  
  <pre><code>main(){cout&lt;&lt;solution("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");}
  </code></pre>