#include          using     namespace     std  ;   // function to check if the substring s[i...j] is a palindrome   bool     isPalindrome  (  string     &  s       int     i       int     j  )     {      while     (  i      <     j  )     {          // if characters at the ends are not equal       // it's not a palindrome      if     (  s  [  i  ]     !=     s  [  j  ])     {      return     false  ;      }      i  ++  ;      j  --  ;      }      return     true  ;   }   int     minChar  (  string     &  s  )     {      int     cnt     =     0  ;      int     i     =     s  .  size  ()     -     1  ;          // iterate from the end of the string checking for the       // longestpalindrome starting from the beginning      while     (  i     >=     0     &&     !  isPalindrome  (  s       0       i  ))     {          i  --  ;      cnt  ++  ;      }          return     cnt  ;   }   int     main  ()     {      string     s     =     'aacecaaaa'  ;      cout      < <     minChar  (  s  );      return     0  ;   }   

   #include         #include         #include         // function to check if the substring s[i...j] is a palindrome   bool     isPalindrome  (  char     s  []     int     i       int     j  )     {      while     (  i      <     j  )     {          // if characters at the ends are not the same       // it's not a palindrome      if     (  s  [  i  ]     !=     s  [  j  ])     {      return     false  ;      }      i  ++  ;      j  --  ;      }      return     true  ;   }   int     minChar  (  char     s  [])     {      int     cnt     =     0  ;      int     i     =     strlen  (  s  )     -     1  ;          // iterate from the end of the string checking for the       // longest palindrome starting from the beginning      while     (  i     >=     0     &&     !  isPalindrome  (  s       0       i  ))     {          i  --  ;      cnt  ++  ;      }          return     cnt  ;   }   int     main  ()     {          char     s  []     =     'aacecaaaa'  ;      printf  (  '%d'       minChar  (  s  ));      return     0  ;   }   

   class   GfG     {      // function to check if the substring       // s[i...j] is a palindrome      static     boolean     isPalindrome  (  String     s       int     i       int     j  )     {      while     (  i      <     j  )     {          // if characters at the ends are not the same       // it's not a palindrome      if     (  s  .  charAt  (  i  )     !=     s  .  charAt  (  j  ))     {      return     false  ;      }      i  ++  ;      j  --  ;      }      return     true  ;      }      static     int     minChar  (  String     s  )     {      int     cnt     =     0  ;      int     i     =     s  .  length  ()     -     1  ;          // iterate from the end of the string checking for the       // longest palindrome starting from the beginning      while     (  i     >=     0     &&     !  isPalindrome  (  s       0       i  ))     {      i  --  ;      cnt  ++  ;      }          return     cnt  ;      }      public     static     void     main  (  String  []     args  )     {      String     s     =     'aacecaaaa'  ;      System  .  out  .  println  (  minChar  (  s  ));      }   }   

   # function to check if the substring s[i...j] is a palindrome   def   isPalindrome  (  s     i     j  ):   while   i    <   j  :   # if characters at the ends are not the same    # it's not a palindrome   if   s  [  i  ]   !=   s  [  j  ]:   return   False   i   +=   1   j   -=   1   return   True   def   minChar  (  s  ):   cnt   =   0   i   =   len  (  s  )   -   1   # iterate from the end of the string checking for the    # longest palindrome starting from the beginning   while   i   >=   0   and   not   isPalindrome  (  s     0     i  ):   i   -=   1   cnt   +=   1   return   cnt   if   __name__   ==   '__main__'  :   s   =   'aacecaaaa'   print  (  minChar  (  s  ))   

   using     System  ;   class     GfG     {      // function to check if the substring s[i...j] is a palindrome      static     bool     isPalindrome  (  string     s       int     i       int     j  )     {      while     (  i      <     j  )     {          // if characters at the ends are not the same       // it's not a palindrome      if     (  s  [  i  ]     !=     s  [  j  ])     {      return     false  ;      }      i  ++  ;      j  --  ;      }      return     true  ;      }      static     int     minChar  (  string     s  )     {      int     cnt     =     0  ;      int     i     =     s  .  Length     -     1  ;          // iterate from the end of the string checking for the longest       // palindrome starting from the beginning      while     (  i     >=     0     &&     !  isPalindrome  (  s       0       i  ))     {      i  --  ;      cnt  ++  ;      }          return     cnt  ;      }      static     void     Main  ()     {          string     s     =     'aacecaaaa'  ;      Console  .  WriteLine  (  minChar  (  s  ));      }   }   

   // function to check if the substring s[i...j] is a palindrome   function     isPalindrome  (  s       i       j  )     {      while     (  i      <     j  )     {          // if characters at the ends are not the same       // it's not a palindrome      if     (  s  [  i  ]     !==     s  [  j  ])     {      return     false  ;      }      i  ++  ;      j  --  ;      }      return     true  ;   }   function     minChar  (  s  )     {      let     cnt     =     0  ;      let     i     =     s  .  length     -     1  ;          // iterate from the end of the string checking for the      // longest palindrome starting from the beginning      while     (  i     >=     0     &&     !  isPalindrome  (  s       0       i  ))     {          i  --  ;      cnt  ++  ;      }          return     cnt  ;   }   // Driver code   let     s     =     'aacecaaaa'  ;   console  .  log  (  minChar  (  s  ));   

   #include          #include          #include         using     namespace     std  ;   vector   <  int  >     computeLPSArray  (  string     &  pat  )     {      int     n     =     pat  .  length  ();      vector   <  int  >     lps  (  n  );      // lps[0] is always 0      lps  [  0  ]     =     0  ;      int     len     =     0  ;      // loop calculates lps[i] for i = 1 to M-1      int     i     =     1  ;      while     (  i      <     n  )     {      // if the characters match increment len      // and set lps[i]      if     (  pat  [  i  ]     ==     pat  [  len  ])     {      len  ++  ;      lps  [  i  ]     =     len  ;      i  ++  ;      }      // if there is a mismatch      else     {      // if len is not zero update len to      // the last known prefix length      if     (  len     !=     0  )     {      len     =     lps  [  len     -     1  ];      }      // no prefix matches set lps[i] to 0      else     {      lps  [  i  ]     =     0  ;      i  ++  ;      }      }      }      return     lps  ;   }   // returns minimum character to be added at   // front to make string palindrome   int     minChar  (  string     &  s  )     {      int     n     =     s  .  length  ();      string     rev     =     s  ;      reverse  (  rev  .  begin  ()     rev  .  end  ());      // get concatenation of string special character      // and reverse string      s     =     s     +     '$'     +     rev  ;      // get LPS array of this concatenated string      vector   <  int  >     lps     =     computeLPSArray  (  s  );      // by subtracting last entry of lps vector from      // string length we will get our result      return     (  n     -     lps  .  back  ());   }   int     main  ()     {      string     s     =     'aacecaaaa'  ;      cout      < <     minChar  (  s  );      return     0  ;   }   

   import     java.util.ArrayList  ;   class   GfG     {      static     int  []     computeLPSArray  (  String     pat  )     {      int     n     =     pat  .  length  ();      int  []     lps     =     new     int  [  n  ]  ;      // lps[0] is always 0      lps  [  0  ]     =     0  ;      int     len     =     0  ;      // loop calculates lps[i] for i = 1 to n-1      int     i     =     1  ;      while     (  i      <     n  )     {      // if the characters match increment len      // and set lps[i]      if     (  pat  .  charAt  (  i  )     ==     pat  .  charAt  (  len  ))     {      len  ++  ;      lps  [  i  ]     =     len  ;      i  ++  ;      }      // if there is a mismatch      else     {      // if len is not zero update len to      // the last known prefix length      if     (  len     !=     0  )     {      len     =     lps  [  len     -     1  ]  ;      }      // no prefix matches set lps[i] to 0      else     {      lps  [  i  ]     =     0  ;      i  ++  ;      }      }      }      return     lps  ;      }      // returns minimum character to be added at      // front to make string palindrome      static     int     minChar  (  String     s  )     {      int     n     =     s  .  length  ();      String     rev      =     new     StringBuilder  (  s  ).  reverse  ().  toString  ();      // get concatenation of string special character      // and reverse string      s     =     s     +     '$'     +     rev  ;      // get LPS array of this concatenated string      int  []     lps     =     computeLPSArray  (  s  );      // by subtracting last entry of lps array from      // string length we will get our result      return     (  n     -     lps  [  lps  .  length     -     1  ]  );      }      public     static     void     main  (  String  []     args  )     {      String     s     =     'aacecaaaa'  ;      System  .  out  .  println  (  minChar  (  s  ));      }   }   

   def   computeLPSArray  (  pat  ):   n   =   len  (  pat  )   lps   =   [  0  ]   *   n   # lps[0] is always 0   len_lps   =   0   # loop calculates lps[i] for i = 1 to n-1   i   =   1   while   i    <   n  :   # if the characters match increment len   # and set lps[i]   if   pat  [  i  ]   ==   pat  [  len_lps  ]:   len_lps   +=   1   lps  [  i  ]   =   len_lps   i   +=   1   # if there is a mismatch   else  :   # if len is not zero update len to    # the last known prefix length   if   len_lps   !=   0  :   len_lps   =   lps  [  len_lps   -   1  ]   # no prefix matches set lps[i] to 0   else  :   lps  [  i  ]   =   0   i   +=   1   return   lps   # returns minimum character to be added at   # front to make string palindrome   def   minChar  (  s  ):   n   =   len  (  s  )   rev   =   s  [::  -  1  ]   # get concatenation of string special character   # and reverse string   s   =   s   +   '$'   +   rev   # get LPS array of this concatenated string   lps   =   computeLPSArray  (  s  )   # by subtracting last entry of lps array from   # string length we will get our result   return   n   -   lps  [  -  1  ]   if   __name__   ==   '__main__'  :   s   =   'aacecaaaa'   print  (  minChar  (  s  ))   

   using     System  ;   class     GfG     {      static     int  []     computeLPSArray  (  string     pat  )     {      int     n     =     pat  .  Length  ;      int  []     lps     =     new     int  [  n  ];      // lps[0] is always 0      lps  [  0  ]     =     0  ;      int     len     =     0  ;      // loop calculates lps[i] for i = 1 to n-1      int     i     =     1  ;      while     (  i      <     n  )     {      // if the characters match increment len      // and set lps[i]      if     (  pat  [  i  ]     ==     pat  [  len  ])     {      len  ++  ;      lps  [  i  ]     =     len  ;      i  ++  ;      }      // if there is a mismatch      else     {      // if len is not zero update len to      // the last known prefix length      if     (  len     !=     0  )     {      len     =     lps  [  len     -     1  ];      }      // no prefix matches set lps[i] to 0      else     {      lps  [  i  ]     =     0  ;      i  ++  ;      }      }      }      return     lps  ;      }      // minimum character to be added at      // front to make string palindrome      static     int     minChar  (  string     s  )     {      int     n     =     s  .  Length  ;      char  []     charArray     =     s  .  ToCharArray  ();      Array  .  Reverse  (  charArray  );      string     rev     =     new     string  (  charArray  );      // get concatenation of string special character      // and reverse string      s     =     s     +     '$'     +     rev  ;      // get LPS array of this concatenated string      int  []     lps     =     computeLPSArray  (  s  );      // by subtracting last entry of lps array from      // string length we will get our result      return     n     -     lps  [  lps  .  Length     -     1  ];      }      static     void     Main  ()     {      string     s     =     'aacecaaaa'  ;      Console  .  WriteLine  (  minChar  (  s  ));      }   }   

   function     computeLPSArray  (  pat  )     {      let     n     =     pat  .  length  ;      let     lps     =     new     Array  (  n  ).  fill  (  0  );      // lps[0] is always 0      let     len     =     0  ;      // loop calculates lps[i] for i = 1 to n-1      let     i     =     1  ;      while     (  i      <     n  )     {      // if the characters match increment len      // and set lps[i]      if     (  pat  [  i  ]     ===     pat  [  len  ])     {      len  ++  ;      lps  [  i  ]     =     len  ;      i  ++  ;      }      // if there is a mismatch      else     {      // if len is not zero update len to      // the last known prefix length      if     (  len     !==     0  )     {      len     =     lps  [  len     -     1  ];      }      // no prefix matches set lps[i] to 0      else     {      lps  [  i  ]     =     0  ;      i  ++  ;      }      }      }      return     lps  ;   }   // returns minimum character to be added at   // front to make string palindrome   function     minChar  (  s  )     {      let     n     =     s  .  length  ;      let     rev     =     s  .  split  (  ''  ).  reverse  ().  join  (  ''  );      // get concatenation of string special character      // and reverse string      s     =     s     +     '$'     +     rev  ;      // get LPS array of this concatenated string      let     lps     =     computeLPSArray  (  s  );      // by subtracting last entry of lps array from      // string length we will get our result      return     n     -     lps  [  lps  .  length     -     1  ];   }   // Driver Code   let     s     =     'aacecaaaa'  ;   console  .  log  (  minChar  (  s  ));   

   #include          #include         #include         using     namespace     std  ;   // manacher's algorithm for finding longest    // palindromic substrings   class     manacher     {   public  :      // array to store palindrome lengths centered       // at each position      vector   <  int  >     p  ;      // modified string with separators and sentinels      string     ms  ;         manacher  (  string     &  s  )     {      ms     =     '@'  ;      for     (  char     c     :     s  )     {      ms     +=     '#'     +     string  (  1       c  );      }      ms     +=     '#$'  ;      runManacher  ();      }      // core Manacher's algorithm      void     runManacher  ()     {      int     n     =     ms  .  size  ();      p  .  assign  (  n       0  );      int     l     =     0       r     =     0  ;      for     (  int     i     =     1  ;     i      <     n     -     1  ;     ++  i  )     {      if     (  i      <     r  )      p  [  i  ]     =     min  (  r     -     i       p  [  r     +     l     -     i  ]);      // expand around the current center      while     (  ms  [  i     +     1     +     p  [  i  ]]     ==     ms  [  i     -     1     -     p  [  i  ]])      ++  p  [  i  ];      // update center if palindrome goes beyond      // current right boundary      if     (  i     +     p  [  i  ]     >     r  )     {      l     =     i     -     p  [  i  ];      r     =     i     +     p  [  i  ];      }      }      }      // returns the length of the longest palindrome      // centered at given position      int     getLongest  (  int     cen       int     odd  )     {      int     pos     =     2     *     cen     +     2     +     !  odd  ;      return     p  [  pos  ];      }      // checks whether substring s[l...r] is a palindrome      bool     check  (  int     l       int     r  )     {      int     len     =     r     -     l     +     1  ;      int     longest     =     getLongest  ((  l     +     r  )     /     2       len     %     2  );      return     len      <=     longest  ;      }   };   // returns the minimum number of characters to add at the    // front to make the given string a palindrome   int     minChar  (  string     &  s  )     {      int     n     =     s  .  size  ();      manacher     m  (  s  );      // scan from the end to find the longest       // palindromic prefix      for     (  int     i     =     n     -     1  ;     i     >=     0  ;     --  i  )     {      if     (  m  .  check  (  0       i  ))      return     n     -     (  i     +     1  );      }      return     n     -     1  ;   }   int     main  ()     {      string     s     =     'aacecaaaa'  ;      cout      < <     minChar  (  s  )      < <     endl  ;      return     0  ;   }   

   class   GfG     {          // manacher's algorithm for finding longest       // palindromic substrings      static     class   manacher     {      // array to store palindrome lengths centered       // at each position      int  []     p  ;      // modified string with separators and sentinels      String     ms  ;      manacher  (  String     s  )     {      StringBuilder     sb     =     new     StringBuilder  (  '@'  );      for     (  char     c     :     s  .  toCharArray  ())     {      sb  .  append  (  '#'  ).  append  (  c  );      }      sb  .  append  (  '#$'  );      ms     =     sb  .  toString  ();      runManacher  ();      }      // core Manacher's algorithm      void     runManacher  ()     {      int     n     =     ms  .  length  ();      p     =     new     int  [  n  ]  ;      int     l     =     0       r     =     0  ;      for     (  int     i     =     1  ;     i      <     n     -     1  ;     ++  i  )     {      if     (  i      <     r  )      p  [  i  ]     =     Math  .  min  (  r     -     i       p  [  r     +     l     -     i  ]  );      // expand around the current center      while     (  ms  .  charAt  (  i     +     1     +     p  [  i  ]  )     ==     ms  .  charAt  (  i     -     1     -     p  [  i  ]  ))      p  [  i  ]++  ;      // update center if palindrome goes beyond       // current right boundary      if     (  i     +     p  [  i  ]     >     r  )     {      l     =     i     -     p  [  i  ]  ;      r     =     i     +     p  [  i  ]  ;      }      }      }      // returns the length of the longest palindrome       // centered at given position      int     getLongest  (  int     cen       int     odd  )     {      int     pos     =     2     *     cen     +     2     +     (  odd     ==     0     ?     1     :     0  );      return     p  [  pos  ]  ;      }      // checks whether substring s[l...r] is a palindrome      boolean     check  (  int     l       int     r  )     {      int     len     =     r     -     l     +     1  ;      int     longest     =     getLongest  ((  l     +     r  )     /     2       len     %     2  );      return     len      <=     longest  ;      }      }      // returns the minimum number of characters to add at the       // front to make the given string a palindrome      static     int     minChar  (  String     s  )     {      int     n     =     s  .  length  ();      manacher     m     =     new     manacher  (  s  );      // scan from the end to find the longest       // palindromic prefix      for     (  int     i     =     n     -     1  ;     i     >=     0  ;     --  i  )     {      if     (  m  .  check  (  0       i  ))      return     n     -     (  i     +     1  );      }      return     n     -     1  ;      }      public     static     void     main  (  String  []     args  )     {      String     s     =     'aacecaaaa'  ;      System  .  out  .  println  (  minChar  (  s  ));      }   }   

   # manacher's algorithm for finding longest    # palindromic substrings   class   manacher  :   # array to store palindrome lengths centered    # at each position   def   __init__  (  self     s  ):   # modified string with separators and sentinels   self  .  ms   =   '@'   for   c   in   s  :   self  .  ms   +=   '#'   +   c   self  .  ms   +=   '#$'   self  .  p   =   []   self  .  runManacher  ()   # core Manacher's algorithm   def   runManacher  (  self  ):   n   =   len  (  self  .  ms  )   self  .  p   =   [  0  ]   *   n   l   =   r   =   0   for   i   in   range  (  1     n   -   1  ):   if   i    <   r  :   self  .  p  [  i  ]   =   min  (  r   -   i     self  .  p  [  r   +   l   -   i  ])   # expand around the current center   while   self  .  ms  [  i   +   1   +   self  .  p  [  i  ]]   ==   self  .  ms  [  i   -   1   -   self  .  p  [  i  ]]:   self  .  p  [  i  ]   +=   1   # update center if palindrome goes beyond    # current right boundary   if   i   +   self  .  p  [  i  ]   >   r  :   l   =   i   -   self  .  p  [  i  ]   r   =   i   +   self  .  p  [  i  ]   # returns the length of the longest palindrome    # centered at given position   def   getLongest  (  self     cen     odd  ):   pos   =   2   *   cen   +   2   +   (  0   if   odd   else   1  )   return   self  .  p  [  pos  ]   # checks whether substring s[l...r] is a palindrome   def   check  (  self     l     r  ):   length   =   r   -   l   +   1   longest   =   self  .  getLongest  ((  l   +   r  )   //   2     length   %   2  )   return   length    <=   longest   # returns the minimum number of characters to add at the    # front to make the given string a palindrome   def   minChar  (  s  ):   n   =   len  (  s  )   m   =   manacher  (  s  )   # scan from the end to find the longest    # palindromic prefix   for   i   in   range  (  n   -   1     -  1     -  1  ):   if   m  .  check  (  0     i  ):   return   n   -   (  i   +   1  )   return   n   -   1   if   __name__   ==   '__main__'  :   s   =   'aacecaaaa'   print  (  minChar  (  s  ))   

   using     System  ;   class     GfG     {          // manacher's algorithm for finding longest       // palindromic substrings      class     manacher     {      // array to store palindrome lengths centered       // at each position      public     int  []     p  ;      // modified string with separators and sentinels      public     string     ms  ;      public     manacher  (  string     s  )     {      ms     =     '@'  ;      foreach     (  char     c     in     s  )     {      ms     +=     '#'     +     c  ;      }      ms     +=     '#$'  ;      runManacher  ();      }      // core Manacher's algorithm      void     runManacher  ()     {      int     n     =     ms  .  Length  ;      p     =     new     int  [  n  ];      int     l     =     0       r     =     0  ;      for     (  int     i     =     1  ;     i      <     n     -     1  ;     ++  i  )     {      if     (  i      <     r  )      p  [  i  ]     =     Math  .  Min  (  r     -     i       p  [  r     +     l     -     i  ]);      // expand around the current center      while     (  ms  [  i     +     1     +     p  [  i  ]]     ==     ms  [  i     -     1     -     p  [  i  ]])      p  [  i  ]  ++  ;      // update center if palindrome goes beyond       // current right boundary      if     (  i     +     p  [  i  ]     >     r  )     {      l     =     i     -     p  [  i  ];      r     =     i     +     p  [  i  ];      }      }      }      // returns the length of the longest palindrome       // centered at given position      public     int     getLongest  (  int     cen       int     odd  )     {      int     pos     =     2     *     cen     +     2     +     (  odd     ==     0     ?     1     :     0  );      return     p  [  pos  ];      }      // checks whether substring s[l...r] is a palindrome      public     bool     check  (  int     l       int     r  )     {      int     len     =     r     -     l     +     1  ;      int     longest     =     getLongest  ((  l     +     r  )     /     2       len     %     2  );      return     len      <=     longest  ;      }      }      // returns the minimum number of characters to add at the       // front to make the given string a palindrome      static     int     minChar  (  string     s  )     {      int     n     =     s  .  Length  ;      manacher     m     =     new     manacher  (  s  );      // scan from the end to find the longest       // palindromic prefix      for     (  int     i     =     n     -     1  ;     i     >=     0  ;     --  i  )     {      if     (  m  .  check  (  0       i  ))      return     n     -     (  i     +     1  );      }      return     n     -     1  ;      }      static     void     Main  ()     {      string     s     =     'aacecaaaa'  ;      Console  .  WriteLine  (  minChar  (  s  ));      }   }   

   // manacher's algorithm for finding longest    // palindromic substrings   class     manacher     {          // array to store palindrome lengths centered       // at each position      constructor  (  s  )     {      // modified string with separators and sentinels      this  .  ms     =     '@'  ;      for     (  let     c     of     s  )     {      this  .  ms     +=     '#'     +     c  ;      }      this  .  ms     +=     '#$'  ;      this  .  p     =     [];      this  .  runManacher  ();      }      // core Manacher's algorithm      runManacher  ()     {      const     n     =     this  .  ms  .  length  ;      this  .  p     =     new     Array  (  n  ).  fill  (  0  );      let     l     =     0       r     =     0  ;      for     (  let     i     =     1  ;     i      <     n     -     1  ;     ++  i  )     {      if     (  i      <     r  )      this  .  p  [  i  ]     =     Math  .  min  (  r     -     i       this  .  p  [  r     +     l     -     i  ]);      // expand around the current center      while     (  this  .  ms  [  i     +     1     +     this  .  p  [  i  ]]     ===     this  .  ms  [  i     -     1     -     this  .  p  [  i  ]])      this  .  p  [  i  ]  ++  ;      // update center if palindrome goes beyond       // current right boundary      if     (  i     +     this  .  p  [  i  ]     >     r  )     {      l     =     i     -     this  .  p  [  i  ];      r     =     i     +     this  .  p  [  i  ];      }      }      }      // returns the length of the longest palindrome       // centered at given position      getLongest  (  cen       odd  )     {      const     pos     =     2     *     cen     +     2     +     (  odd     ===     0     ?     1     :     0  );      return     this  .  p  [  pos  ];      }      // checks whether substring s[l...r] is a palindrome      check  (  l       r  )     {      const     len     =     r     -     l     +     1  ;      const     longest     =     this  .  getLongest  (  Math  .  floor  ((  l     +     r  )     /     2  )     len     %     2  );      return     len      <=     longest  ;      }   }   // returns the minimum number of characters to add at the    // front to make the given string a palindrome   function     minChar  (  s  )     {      const     n     =     s  .  length  ;      const     m     =     new     manacher  (  s  );      // scan from the end to find the longest       // palindromic prefix      for     (  let     i     =     n     -     1  ;     i     >=     0  ;     --  i  )     {      if     (  m  .  check  (  0       i  ))      return     n     -     (  i     +     1  );      }      return     n     -     1  ;   }   // Driver Code   const     s     =     'aacecaaaa'  ;   console  .  log  (  minChar  (  s  ));