title: Count the number of Substrings which are Palindromes
body: <p>I am currently attempting to solve a programming question featured on Hackerreank, (Link Here -> <a href="https://www.hackerrank.com/challenges/count-palindromes" rel="nofollow">https://www.hackerrank.com/challenges/count-palindromes</a>). </p>
  
  <p>The question defines a string as composed of lower case characters ( a through z )</p>
  
  <p>K is a number I am provided as input</p>
  
  <p>I am supposed to find the smallest string( definition above ), that  contains K palindrome substrings. (Palindrome is a sequence which when reversed will give the same sequence).</p>
  
  <p>Ok, this makes sense. Now, here's my approach</p>
  
  <p>Suppose I have a string "aaaa", this has 10 palindrome substrings of the form
  a,a,a,a
  aa,aa,aa
  aaa,aaa
  aaaa.
   (Since characters at different indexes are considered unique.)</p>
  
  <p>So if K was given as 10, then the smallest length of string that has 10 palindrome substrings is 4. Hence the answer is 4 (This detail can also be found on the link)</p>
  
  <p>Now I have an approach to solving this problem, which is not giving me the right result. </p>
  
  <p>Suppose the substring length is N, I will obtain the smallest possible value of N, if it contains all the same characters</p>
  
  <p>If I assume this, then the number of:</p>
  
  <p>Size 1 palindrome substrings = N</p>
  
  <p>Size 2 palindrome substrings = N-1</p>
  
  <p>Size 3 palindrome substrings = N-2</p>
  
  <p>..</p>
  
  <p>..</p>
  
  <p>..</p>
  
  <p>Size N palindrome substrings = 1</p>
  
  <p>The number of palindrome substrings can be calculated using this code</p>
  
  <pre><code>index = N
  total = 0
  while N &gt; 0:
      total += N   
      N-=1
  </code></pre>
  
  <p>Step by Step, this code is simply computing the sum of natural numbers from 1 till N</p>
  
  <p>Hence (N * N+1) / 2 is the number of palindrome substrings a number can have. Therefore for a particular N, is (N * N+1) / 2 is equal to K, then N is the answer.</p>
  
  <p>Now a sample case input K is 17</p>
  
  <p>But N * N+1 / 2 will never give a N (Natual Number)</p>
  
  <p>Can anyone tell what is the mistake in my approach. All help is appreciated :) and sorry for the long question</p>
  
  <p>P.S  : I dont really need a solution to the problem, I just want to figure out whats wrong with my algorithm</p>