Find longest Palindrome substring

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
3
down vote

favorite












I am preparing for technical interview and I found this question on geeksforgeeks, but I did not understand their solution. So, I have written my own solution. I want to optimize this code.



#include <iostream>
#include <string>

bool isPalindrome(std::string& str)

for (int i = 0, j = str.length()-1; i<j; ++i, --j)

if (str[i] != str[j])

return false;


return true;


int longestPalindrome(std::string& str, std::string& palindromeStr)

int max = 0, start = 0, end = 0;
for (int i = 0; i < str.length(); ++i)

for (int j = i+1; j < str.length(); ++j)

std::string sub = str.substr(i, j);
if (isPalindrome(sub) && max < sub.length())

max = sub.length();
start = i;
end = j;



palindromeStr = str.substr(start, end);
return max;


int main()

std::string str = "forgeekskeegfor";
std::string palindromeStr;
std::cout << longestPalindrome(str, palindromeStr) << 'n';
std::cout << palindromeStr << 'n';










share|improve this question



























    up vote
    3
    down vote

    favorite












    I am preparing for technical interview and I found this question on geeksforgeeks, but I did not understand their solution. So, I have written my own solution. I want to optimize this code.



    #include <iostream>
    #include <string>

    bool isPalindrome(std::string& str)

    for (int i = 0, j = str.length()-1; i<j; ++i, --j)

    if (str[i] != str[j])

    return false;


    return true;


    int longestPalindrome(std::string& str, std::string& palindromeStr)

    int max = 0, start = 0, end = 0;
    for (int i = 0; i < str.length(); ++i)

    for (int j = i+1; j < str.length(); ++j)

    std::string sub = str.substr(i, j);
    if (isPalindrome(sub) && max < sub.length())

    max = sub.length();
    start = i;
    end = j;



    palindromeStr = str.substr(start, end);
    return max;


    int main()

    std::string str = "forgeekskeegfor";
    std::string palindromeStr;
    std::cout << longestPalindrome(str, palindromeStr) << 'n';
    std::cout << palindromeStr << 'n';










    share|improve this question

























      up vote
      3
      down vote

      favorite









      up vote
      3
      down vote

      favorite











      I am preparing for technical interview and I found this question on geeksforgeeks, but I did not understand their solution. So, I have written my own solution. I want to optimize this code.



      #include <iostream>
      #include <string>

      bool isPalindrome(std::string& str)

      for (int i = 0, j = str.length()-1; i<j; ++i, --j)

      if (str[i] != str[j])

      return false;


      return true;


      int longestPalindrome(std::string& str, std::string& palindromeStr)

      int max = 0, start = 0, end = 0;
      for (int i = 0; i < str.length(); ++i)

      for (int j = i+1; j < str.length(); ++j)

      std::string sub = str.substr(i, j);
      if (isPalindrome(sub) && max < sub.length())

      max = sub.length();
      start = i;
      end = j;



      palindromeStr = str.substr(start, end);
      return max;


      int main()

      std::string str = "forgeekskeegfor";
      std::string palindromeStr;
      std::cout << longestPalindrome(str, palindromeStr) << 'n';
      std::cout << palindromeStr << 'n';










      share|improve this question















      I am preparing for technical interview and I found this question on geeksforgeeks, but I did not understand their solution. So, I have written my own solution. I want to optimize this code.



      #include <iostream>
      #include <string>

      bool isPalindrome(std::string& str)

      for (int i = 0, j = str.length()-1; i<j; ++i, --j)

      if (str[i] != str[j])

      return false;


      return true;


      int longestPalindrome(std::string& str, std::string& palindromeStr)

      int max = 0, start = 0, end = 0;
      for (int i = 0; i < str.length(); ++i)

      for (int j = i+1; j < str.length(); ++j)

      std::string sub = str.substr(i, j);
      if (isPalindrome(sub) && max < sub.length())

      max = sub.length();
      start = i;
      end = j;



      palindromeStr = str.substr(start, end);
      return max;


      int main()

      std::string str = "forgeekskeegfor";
      std::string palindromeStr;
      std::cout << longestPalindrome(str, palindromeStr) << 'n';
      std::cout << palindromeStr << 'n';







      c++ algorithm strings interview-questions palindrome






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Sep 19 at 21:07









      200_success

      125k14145406




      125k14145406










      asked Sep 19 at 10:39









      coder

      905432




      905432




















          3 Answers
          3






          active

          oldest

          votes

















          up vote
          11
          down vote



          accepted










          The code is reasonably clear and obvious, but has some severe inefficiencies.



          First, let's pick up some simple oversights. Both isPalindrome() and longestPalindrome() ought to have internal linkage (using either the static keyword or the anonymous namespace), and the str arguments should be reference to const:



          namespace 
          bool isPalindrome(const std::string& str);
          int longestPalindrome(const std::string& str, std::string& palindromeStr);



          In passing, we can simplify the interface of longestPalindrome(). It doesn't need to return the string and its length; if we simply return the longest palindrome, then obtaining the length is trivial:



           std::string longestPalindrome(const std::string& str);

          // main() can now look like:
          // std::string palindromeStr = longestPalindrome(str);
          // std::cout << palindromeStr.size() << 'n';
          // std::cout << palindromeStr << 'n';


          The next oversight is that std::string::length() returns a std::size_t, so don't compare it with (signed) int:



          for (std::size_t i = 0, j = str.length()-1; i<j; ++i, --j)
          // ^^^^^^^^^^^


          Note that I've left a bug there (that's neatly missed because we always call this with a non-empty string): if str.length() is zero, then j starts at a very large positive value (because the subtraction is unsigned, and wraps).



          BTW, there's a neat way to test a string for symmetry (at the expense of repeating the initial comparisons), using <algorithm>:



          static bool isPalindrome(const std::string& str)

          return std::equal(str.begin(), str.end(), str.rbegin());




          Now to the matter of efficiency. We're creating new string objects for every possible substring of the input. That's a lot of copying. We could reduce that by using std::string_view.



          That's only part of the way towards an efficient solution, though. We really need to change the algorithm. My recommendation is to iterate over each character as a possible mid-point of an embedded palindrome, and at each position, determine what's the longest palindrome possible from there (in most cases, it will be 1 or 2 chars). There's no need to consider longer substrings centred on that position once you have a failing case, so that eliminates much of the unnecessary work we're doing here.



          Hint: for this we can use std::make_reverse_iterator() and std::mismatch().




          Finally, the single test we have in main() isn't really enough. At a minimum, we want examples of odd- and even-length palindromes, and also check that we handle the trivial case of empty string as input.




          Update - using iterators



          I've developed the idea I hinted at in the second section; there's probably a little more scope for reducing duplication:



          #include <algorithm>
          #include <iostream>
          #include <iterator>
          #include <string>
          #include <string_view>

          namespace

          template<typename Iter>
          // requires BidirectionalIterator(Iter)
          void updateBest(Iter forward_start,
          Iter forward_end,
          std::reverse_iterator<Iter> backward_start,
          std::reverse_iterator<Iter> backward_end,
          std::string_view& best_so_far)

          auto span = std::mismatch(forward_start, forward_end,
          backward_start, backward_end);
          auto start = span.second.base();
          auto end = span.first;
          std::string_view candidate &*start, static_cast<std::size_t>(std::distance(start, end)) ;
          if (candidate.size() > best_so_far.size())
          best_so_far = candidate;



          std::string_view longestPalindrome(const std::string& str)

          std::string_view best_so_far;

          // Work out from the middle of the string
          auto const halfway = (str.size() + 1) / 2;

          // first, loop from midpont to end of string (but we can stop
          // when there's no room for a bigger palindrome)
          for (auto i = str.begin() + halfway; i + best_so_far.length()/2 < str.end(); ++i)
          // test for odd-length palindrome
          updateBest(i, str.end(),
          std::make_reverse_iterator(i), str.rend(),
          best_so_far);
          // test for even-length palindrome
          updateBest(i + 1, str.end(),
          std::make_reverse_iterator(i), str.rend(),
          best_so_far);


          // then, loop from midpont to beginning of string (but stop
          // when there's no room for a bigger palindrome)
          for (auto i = str.rbegin() + halfway; i + best_so_far.length()/2 < str.rend(); ++i)
          // test for odd-length palindrome
          updateBest(i.base(), str.end(),
          i, str.rend(),
          best_so_far);
          // test for even-length palindrome
          updateBest(i.base(), str.end(),
          i + 1, str.rend(),
          best_so_far);


          return best_so_far;





          int main()

          for (std::string s: "",
          "forgeekskeegfor",
          "abc abc",
          "forgeeksskeeg",
          "geeksskeegfor" )
          auto palindromeStr = longestPalindrome(s);
          std::cout << "Found palindrome of length " << palindromeStr.size()
          << " in " << s << ": " << palindromeStr << 'n';







          share|improve this answer






















          • How should I know when to declare a function static ?
            – coder
            Sep 20 at 9:11










          • If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static.
            – Toby Speight
            Sep 20 at 9:15

















          up vote
          4
          down vote













          You can avoid checking every string by growing the substring on both ends. That way you can quit the inner for loop as soon as the substring isn't a palindrome anymore and use the previous iteration's substring as the palindrome.



          if(input_str.empty())return 0;
          size_t largest = 1; //if string is not empty then the first character is always a palindrome.
          size_t start = 0;
          std::string_view view = input_str; //create string view to avoid casting each substr call.
          for (int center = 1; center < str.length(); center++)

          //even length palindromes
          for (int j = 1; center - j >= 0 && center + j < str.length(); j++)


          //odd length palindromes
          for (int j = 1; center - j >= 0 && center + j + 1 < str.length; j++)
          center + j + 1 >= str.length()



          Also I use std::string_view to pass to isPalindrome to avoid allocating a new strings every time. std::string_view creates a view into the string and taking the substring of it is a constant time operation with no allocations.






          share|improve this answer






















          • A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication.
            – Toby Speight
            Sep 19 at 16:37










          • This is the insight that people are really looking for during an interview.
            – Tilo
            Sep 19 at 17:56

















          up vote
          3
          down vote













          I suppose that a little optimization could be done by changing the way the substrings are extracted from the main string: the iterations should start from the original string itself and then continue by subtracting characters.



          In this way the first time isPalindrome() returns true, the palindrome is the longest one.



          Here is a little edit to your longestPalindrome function:



          int longestPalindrome(std::string& str, std::string& palindromeStr)

          for (int len = str.length(); len > 1; len--) // One-char strings can't be considered as palindromes...

          for (int j = 0; j <= str.length() - len; j++)

          std::string sub = str.substr(j, j + len);
          if (isPalindrome(sub))

          palindromeStr = sub;
          return len;



          return 0; // It is not a palindrome...






          share|improve this answer






















            Your Answer




            StackExchange.ifUsing("editor", function ()
            return StackExchange.using("mathjaxEditing", function ()
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            );
            );
            , "mathjax-editing");

            StackExchange.ifUsing("editor", function ()
            StackExchange.using("externalEditor", function ()
            StackExchange.using("snippets", function ()
            StackExchange.snippets.init();
            );
            );
            , "code-snippets");

            StackExchange.ready(function()
            var channelOptions =
            tags: "".split(" "),
            id: "196"
            ;
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function()
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled)
            StackExchange.using("snippets", function()
            createEditor();
            );

            else
            createEditor();

            );

            function createEditor()
            StackExchange.prepareEditor(
            heartbeatType: 'answer',
            convertImagesToLinks: false,
            noModals: false,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            );



            );













             

            draft saved


            draft discarded


















            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f203983%2ffind-longest-palindrome-substring%23new-answer', 'question_page');

            );

            Post as a guest






























            3 Answers
            3






            active

            oldest

            votes








            3 Answers
            3






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes








            up vote
            11
            down vote



            accepted










            The code is reasonably clear and obvious, but has some severe inefficiencies.



            First, let's pick up some simple oversights. Both isPalindrome() and longestPalindrome() ought to have internal linkage (using either the static keyword or the anonymous namespace), and the str arguments should be reference to const:



            namespace 
            bool isPalindrome(const std::string& str);
            int longestPalindrome(const std::string& str, std::string& palindromeStr);



            In passing, we can simplify the interface of longestPalindrome(). It doesn't need to return the string and its length; if we simply return the longest palindrome, then obtaining the length is trivial:



             std::string longestPalindrome(const std::string& str);

            // main() can now look like:
            // std::string palindromeStr = longestPalindrome(str);
            // std::cout << palindromeStr.size() << 'n';
            // std::cout << palindromeStr << 'n';


            The next oversight is that std::string::length() returns a std::size_t, so don't compare it with (signed) int:



            for (std::size_t i = 0, j = str.length()-1; i<j; ++i, --j)
            // ^^^^^^^^^^^


            Note that I've left a bug there (that's neatly missed because we always call this with a non-empty string): if str.length() is zero, then j starts at a very large positive value (because the subtraction is unsigned, and wraps).



            BTW, there's a neat way to test a string for symmetry (at the expense of repeating the initial comparisons), using <algorithm>:



            static bool isPalindrome(const std::string& str)

            return std::equal(str.begin(), str.end(), str.rbegin());




            Now to the matter of efficiency. We're creating new string objects for every possible substring of the input. That's a lot of copying. We could reduce that by using std::string_view.



            That's only part of the way towards an efficient solution, though. We really need to change the algorithm. My recommendation is to iterate over each character as a possible mid-point of an embedded palindrome, and at each position, determine what's the longest palindrome possible from there (in most cases, it will be 1 or 2 chars). There's no need to consider longer substrings centred on that position once you have a failing case, so that eliminates much of the unnecessary work we're doing here.



            Hint: for this we can use std::make_reverse_iterator() and std::mismatch().




            Finally, the single test we have in main() isn't really enough. At a minimum, we want examples of odd- and even-length palindromes, and also check that we handle the trivial case of empty string as input.




            Update - using iterators



            I've developed the idea I hinted at in the second section; there's probably a little more scope for reducing duplication:



            #include <algorithm>
            #include <iostream>
            #include <iterator>
            #include <string>
            #include <string_view>

            namespace

            template<typename Iter>
            // requires BidirectionalIterator(Iter)
            void updateBest(Iter forward_start,
            Iter forward_end,
            std::reverse_iterator<Iter> backward_start,
            std::reverse_iterator<Iter> backward_end,
            std::string_view& best_so_far)

            auto span = std::mismatch(forward_start, forward_end,
            backward_start, backward_end);
            auto start = span.second.base();
            auto end = span.first;
            std::string_view candidate &*start, static_cast<std::size_t>(std::distance(start, end)) ;
            if (candidate.size() > best_so_far.size())
            best_so_far = candidate;



            std::string_view longestPalindrome(const std::string& str)

            std::string_view best_so_far;

            // Work out from the middle of the string
            auto const halfway = (str.size() + 1) / 2;

            // first, loop from midpont to end of string (but we can stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.begin() + halfway; i + best_so_far.length()/2 < str.end(); ++i)
            // test for odd-length palindrome
            updateBest(i, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i + 1, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);


            // then, loop from midpont to beginning of string (but stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.rbegin() + halfway; i + best_so_far.length()/2 < str.rend(); ++i)
            // test for odd-length palindrome
            updateBest(i.base(), str.end(),
            i, str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i.base(), str.end(),
            i + 1, str.rend(),
            best_so_far);


            return best_so_far;





            int main()

            for (std::string s: "",
            "forgeekskeegfor",
            "abc abc",
            "forgeeksskeeg",
            "geeksskeegfor" )
            auto palindromeStr = longestPalindrome(s);
            std::cout << "Found palindrome of length " << palindromeStr.size()
            << " in " << s << ": " << palindromeStr << 'n';







            share|improve this answer






















            • How should I know when to declare a function static ?
              – coder
              Sep 20 at 9:11










            • If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static.
              – Toby Speight
              Sep 20 at 9:15














            up vote
            11
            down vote



            accepted










            The code is reasonably clear and obvious, but has some severe inefficiencies.



            First, let's pick up some simple oversights. Both isPalindrome() and longestPalindrome() ought to have internal linkage (using either the static keyword or the anonymous namespace), and the str arguments should be reference to const:



            namespace 
            bool isPalindrome(const std::string& str);
            int longestPalindrome(const std::string& str, std::string& palindromeStr);



            In passing, we can simplify the interface of longestPalindrome(). It doesn't need to return the string and its length; if we simply return the longest palindrome, then obtaining the length is trivial:



             std::string longestPalindrome(const std::string& str);

            // main() can now look like:
            // std::string palindromeStr = longestPalindrome(str);
            // std::cout << palindromeStr.size() << 'n';
            // std::cout << palindromeStr << 'n';


            The next oversight is that std::string::length() returns a std::size_t, so don't compare it with (signed) int:



            for (std::size_t i = 0, j = str.length()-1; i<j; ++i, --j)
            // ^^^^^^^^^^^


            Note that I've left a bug there (that's neatly missed because we always call this with a non-empty string): if str.length() is zero, then j starts at a very large positive value (because the subtraction is unsigned, and wraps).



            BTW, there's a neat way to test a string for symmetry (at the expense of repeating the initial comparisons), using <algorithm>:



            static bool isPalindrome(const std::string& str)

            return std::equal(str.begin(), str.end(), str.rbegin());




            Now to the matter of efficiency. We're creating new string objects for every possible substring of the input. That's a lot of copying. We could reduce that by using std::string_view.



            That's only part of the way towards an efficient solution, though. We really need to change the algorithm. My recommendation is to iterate over each character as a possible mid-point of an embedded palindrome, and at each position, determine what's the longest palindrome possible from there (in most cases, it will be 1 or 2 chars). There's no need to consider longer substrings centred on that position once you have a failing case, so that eliminates much of the unnecessary work we're doing here.



            Hint: for this we can use std::make_reverse_iterator() and std::mismatch().




            Finally, the single test we have in main() isn't really enough. At a minimum, we want examples of odd- and even-length palindromes, and also check that we handle the trivial case of empty string as input.




            Update - using iterators



            I've developed the idea I hinted at in the second section; there's probably a little more scope for reducing duplication:



            #include <algorithm>
            #include <iostream>
            #include <iterator>
            #include <string>
            #include <string_view>

            namespace

            template<typename Iter>
            // requires BidirectionalIterator(Iter)
            void updateBest(Iter forward_start,
            Iter forward_end,
            std::reverse_iterator<Iter> backward_start,
            std::reverse_iterator<Iter> backward_end,
            std::string_view& best_so_far)

            auto span = std::mismatch(forward_start, forward_end,
            backward_start, backward_end);
            auto start = span.second.base();
            auto end = span.first;
            std::string_view candidate &*start, static_cast<std::size_t>(std::distance(start, end)) ;
            if (candidate.size() > best_so_far.size())
            best_so_far = candidate;



            std::string_view longestPalindrome(const std::string& str)

            std::string_view best_so_far;

            // Work out from the middle of the string
            auto const halfway = (str.size() + 1) / 2;

            // first, loop from midpont to end of string (but we can stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.begin() + halfway; i + best_so_far.length()/2 < str.end(); ++i)
            // test for odd-length palindrome
            updateBest(i, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i + 1, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);


            // then, loop from midpont to beginning of string (but stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.rbegin() + halfway; i + best_so_far.length()/2 < str.rend(); ++i)
            // test for odd-length palindrome
            updateBest(i.base(), str.end(),
            i, str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i.base(), str.end(),
            i + 1, str.rend(),
            best_so_far);


            return best_so_far;





            int main()

            for (std::string s: "",
            "forgeekskeegfor",
            "abc abc",
            "forgeeksskeeg",
            "geeksskeegfor" )
            auto palindromeStr = longestPalindrome(s);
            std::cout << "Found palindrome of length " << palindromeStr.size()
            << " in " << s << ": " << palindromeStr << 'n';







            share|improve this answer






















            • How should I know when to declare a function static ?
              – coder
              Sep 20 at 9:11










            • If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static.
              – Toby Speight
              Sep 20 at 9:15












            up vote
            11
            down vote



            accepted







            up vote
            11
            down vote



            accepted






            The code is reasonably clear and obvious, but has some severe inefficiencies.



            First, let's pick up some simple oversights. Both isPalindrome() and longestPalindrome() ought to have internal linkage (using either the static keyword or the anonymous namespace), and the str arguments should be reference to const:



            namespace 
            bool isPalindrome(const std::string& str);
            int longestPalindrome(const std::string& str, std::string& palindromeStr);



            In passing, we can simplify the interface of longestPalindrome(). It doesn't need to return the string and its length; if we simply return the longest palindrome, then obtaining the length is trivial:



             std::string longestPalindrome(const std::string& str);

            // main() can now look like:
            // std::string palindromeStr = longestPalindrome(str);
            // std::cout << palindromeStr.size() << 'n';
            // std::cout << palindromeStr << 'n';


            The next oversight is that std::string::length() returns a std::size_t, so don't compare it with (signed) int:



            for (std::size_t i = 0, j = str.length()-1; i<j; ++i, --j)
            // ^^^^^^^^^^^


            Note that I've left a bug there (that's neatly missed because we always call this with a non-empty string): if str.length() is zero, then j starts at a very large positive value (because the subtraction is unsigned, and wraps).



            BTW, there's a neat way to test a string for symmetry (at the expense of repeating the initial comparisons), using <algorithm>:



            static bool isPalindrome(const std::string& str)

            return std::equal(str.begin(), str.end(), str.rbegin());




            Now to the matter of efficiency. We're creating new string objects for every possible substring of the input. That's a lot of copying. We could reduce that by using std::string_view.



            That's only part of the way towards an efficient solution, though. We really need to change the algorithm. My recommendation is to iterate over each character as a possible mid-point of an embedded palindrome, and at each position, determine what's the longest palindrome possible from there (in most cases, it will be 1 or 2 chars). There's no need to consider longer substrings centred on that position once you have a failing case, so that eliminates much of the unnecessary work we're doing here.



            Hint: for this we can use std::make_reverse_iterator() and std::mismatch().




            Finally, the single test we have in main() isn't really enough. At a minimum, we want examples of odd- and even-length palindromes, and also check that we handle the trivial case of empty string as input.




            Update - using iterators



            I've developed the idea I hinted at in the second section; there's probably a little more scope for reducing duplication:



            #include <algorithm>
            #include <iostream>
            #include <iterator>
            #include <string>
            #include <string_view>

            namespace

            template<typename Iter>
            // requires BidirectionalIterator(Iter)
            void updateBest(Iter forward_start,
            Iter forward_end,
            std::reverse_iterator<Iter> backward_start,
            std::reverse_iterator<Iter> backward_end,
            std::string_view& best_so_far)

            auto span = std::mismatch(forward_start, forward_end,
            backward_start, backward_end);
            auto start = span.second.base();
            auto end = span.first;
            std::string_view candidate &*start, static_cast<std::size_t>(std::distance(start, end)) ;
            if (candidate.size() > best_so_far.size())
            best_so_far = candidate;



            std::string_view longestPalindrome(const std::string& str)

            std::string_view best_so_far;

            // Work out from the middle of the string
            auto const halfway = (str.size() + 1) / 2;

            // first, loop from midpont to end of string (but we can stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.begin() + halfway; i + best_so_far.length()/2 < str.end(); ++i)
            // test for odd-length palindrome
            updateBest(i, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i + 1, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);


            // then, loop from midpont to beginning of string (but stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.rbegin() + halfway; i + best_so_far.length()/2 < str.rend(); ++i)
            // test for odd-length palindrome
            updateBest(i.base(), str.end(),
            i, str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i.base(), str.end(),
            i + 1, str.rend(),
            best_so_far);


            return best_so_far;





            int main()

            for (std::string s: "",
            "forgeekskeegfor",
            "abc abc",
            "forgeeksskeeg",
            "geeksskeegfor" )
            auto palindromeStr = longestPalindrome(s);
            std::cout << "Found palindrome of length " << palindromeStr.size()
            << " in " << s << ": " << palindromeStr << 'n';







            share|improve this answer














            The code is reasonably clear and obvious, but has some severe inefficiencies.



            First, let's pick up some simple oversights. Both isPalindrome() and longestPalindrome() ought to have internal linkage (using either the static keyword or the anonymous namespace), and the str arguments should be reference to const:



            namespace 
            bool isPalindrome(const std::string& str);
            int longestPalindrome(const std::string& str, std::string& palindromeStr);



            In passing, we can simplify the interface of longestPalindrome(). It doesn't need to return the string and its length; if we simply return the longest palindrome, then obtaining the length is trivial:



             std::string longestPalindrome(const std::string& str);

            // main() can now look like:
            // std::string palindromeStr = longestPalindrome(str);
            // std::cout << palindromeStr.size() << 'n';
            // std::cout << palindromeStr << 'n';


            The next oversight is that std::string::length() returns a std::size_t, so don't compare it with (signed) int:



            for (std::size_t i = 0, j = str.length()-1; i<j; ++i, --j)
            // ^^^^^^^^^^^


            Note that I've left a bug there (that's neatly missed because we always call this with a non-empty string): if str.length() is zero, then j starts at a very large positive value (because the subtraction is unsigned, and wraps).



            BTW, there's a neat way to test a string for symmetry (at the expense of repeating the initial comparisons), using <algorithm>:



            static bool isPalindrome(const std::string& str)

            return std::equal(str.begin(), str.end(), str.rbegin());




            Now to the matter of efficiency. We're creating new string objects for every possible substring of the input. That's a lot of copying. We could reduce that by using std::string_view.



            That's only part of the way towards an efficient solution, though. We really need to change the algorithm. My recommendation is to iterate over each character as a possible mid-point of an embedded palindrome, and at each position, determine what's the longest palindrome possible from there (in most cases, it will be 1 or 2 chars). There's no need to consider longer substrings centred on that position once you have a failing case, so that eliminates much of the unnecessary work we're doing here.



            Hint: for this we can use std::make_reverse_iterator() and std::mismatch().




            Finally, the single test we have in main() isn't really enough. At a minimum, we want examples of odd- and even-length palindromes, and also check that we handle the trivial case of empty string as input.




            Update - using iterators



            I've developed the idea I hinted at in the second section; there's probably a little more scope for reducing duplication:



            #include <algorithm>
            #include <iostream>
            #include <iterator>
            #include <string>
            #include <string_view>

            namespace

            template<typename Iter>
            // requires BidirectionalIterator(Iter)
            void updateBest(Iter forward_start,
            Iter forward_end,
            std::reverse_iterator<Iter> backward_start,
            std::reverse_iterator<Iter> backward_end,
            std::string_view& best_so_far)

            auto span = std::mismatch(forward_start, forward_end,
            backward_start, backward_end);
            auto start = span.second.base();
            auto end = span.first;
            std::string_view candidate &*start, static_cast<std::size_t>(std::distance(start, end)) ;
            if (candidate.size() > best_so_far.size())
            best_so_far = candidate;



            std::string_view longestPalindrome(const std::string& str)

            std::string_view best_so_far;

            // Work out from the middle of the string
            auto const halfway = (str.size() + 1) / 2;

            // first, loop from midpont to end of string (but we can stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.begin() + halfway; i + best_so_far.length()/2 < str.end(); ++i)
            // test for odd-length palindrome
            updateBest(i, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i + 1, str.end(),
            std::make_reverse_iterator(i), str.rend(),
            best_so_far);


            // then, loop from midpont to beginning of string (but stop
            // when there's no room for a bigger palindrome)
            for (auto i = str.rbegin() + halfway; i + best_so_far.length()/2 < str.rend(); ++i)
            // test for odd-length palindrome
            updateBest(i.base(), str.end(),
            i, str.rend(),
            best_so_far);
            // test for even-length palindrome
            updateBest(i.base(), str.end(),
            i + 1, str.rend(),
            best_so_far);


            return best_so_far;





            int main()

            for (std::string s: "",
            "forgeekskeegfor",
            "abc abc",
            "forgeeksskeeg",
            "geeksskeegfor" )
            auto palindromeStr = longestPalindrome(s);
            std::cout << "Found palindrome of length " << palindromeStr.size()
            << " in " << s << ": " << palindromeStr << 'n';








            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Sep 20 at 17:44

























            answered Sep 19 at 11:44









            Toby Speight

            19.5k43699




            19.5k43699











            • How should I know when to declare a function static ?
              – coder
              Sep 20 at 9:11










            • If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static.
              – Toby Speight
              Sep 20 at 9:15
















            • How should I know when to declare a function static ?
              – coder
              Sep 20 at 9:11










            • If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static.
              – Toby Speight
              Sep 20 at 9:15















            How should I know when to declare a function static ?
            – coder
            Sep 20 at 9:11




            How should I know when to declare a function static ?
            – coder
            Sep 20 at 9:11












            If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static.
            – Toby Speight
            Sep 20 at 9:15




            If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static.
            – Toby Speight
            Sep 20 at 9:15












            up vote
            4
            down vote













            You can avoid checking every string by growing the substring on both ends. That way you can quit the inner for loop as soon as the substring isn't a palindrome anymore and use the previous iteration's substring as the palindrome.



            if(input_str.empty())return 0;
            size_t largest = 1; //if string is not empty then the first character is always a palindrome.
            size_t start = 0;
            std::string_view view = input_str; //create string view to avoid casting each substr call.
            for (int center = 1; center < str.length(); center++)

            //even length palindromes
            for (int j = 1; center - j >= 0 && center + j < str.length(); j++)


            //odd length palindromes
            for (int j = 1; center - j >= 0 && center + j + 1 < str.length; j++)
            center + j + 1 >= str.length()



            Also I use std::string_view to pass to isPalindrome to avoid allocating a new strings every time. std::string_view creates a view into the string and taking the substring of it is a constant time operation with no allocations.






            share|improve this answer






















            • A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication.
              – Toby Speight
              Sep 19 at 16:37










            • This is the insight that people are really looking for during an interview.
              – Tilo
              Sep 19 at 17:56














            up vote
            4
            down vote













            You can avoid checking every string by growing the substring on both ends. That way you can quit the inner for loop as soon as the substring isn't a palindrome anymore and use the previous iteration's substring as the palindrome.



            if(input_str.empty())return 0;
            size_t largest = 1; //if string is not empty then the first character is always a palindrome.
            size_t start = 0;
            std::string_view view = input_str; //create string view to avoid casting each substr call.
            for (int center = 1; center < str.length(); center++)

            //even length palindromes
            for (int j = 1; center - j >= 0 && center + j < str.length(); j++)


            //odd length palindromes
            for (int j = 1; center - j >= 0 && center + j + 1 < str.length; j++)
            center + j + 1 >= str.length()



            Also I use std::string_view to pass to isPalindrome to avoid allocating a new strings every time. std::string_view creates a view into the string and taking the substring of it is a constant time operation with no allocations.






            share|improve this answer






















            • A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication.
              – Toby Speight
              Sep 19 at 16:37










            • This is the insight that people are really looking for during an interview.
              – Tilo
              Sep 19 at 17:56












            up vote
            4
            down vote










            up vote
            4
            down vote









            You can avoid checking every string by growing the substring on both ends. That way you can quit the inner for loop as soon as the substring isn't a palindrome anymore and use the previous iteration's substring as the palindrome.



            if(input_str.empty())return 0;
            size_t largest = 1; //if string is not empty then the first character is always a palindrome.
            size_t start = 0;
            std::string_view view = input_str; //create string view to avoid casting each substr call.
            for (int center = 1; center < str.length(); center++)

            //even length palindromes
            for (int j = 1; center - j >= 0 && center + j < str.length(); j++)


            //odd length palindromes
            for (int j = 1; center - j >= 0 && center + j + 1 < str.length; j++)
            center + j + 1 >= str.length()



            Also I use std::string_view to pass to isPalindrome to avoid allocating a new strings every time. std::string_view creates a view into the string and taking the substring of it is a constant time operation with no allocations.






            share|improve this answer














            You can avoid checking every string by growing the substring on both ends. That way you can quit the inner for loop as soon as the substring isn't a palindrome anymore and use the previous iteration's substring as the palindrome.



            if(input_str.empty())return 0;
            size_t largest = 1; //if string is not empty then the first character is always a palindrome.
            size_t start = 0;
            std::string_view view = input_str; //create string view to avoid casting each substr call.
            for (int center = 1; center < str.length(); center++)

            //even length palindromes
            for (int j = 1; center - j >= 0 && center + j < str.length(); j++)


            //odd length palindromes
            for (int j = 1; center - j >= 0 && center + j + 1 < str.length; j++)
            center + j + 1 >= str.length()



            Also I use std::string_view to pass to isPalindrome to avoid allocating a new strings every time. std::string_view creates a view into the string and taking the substring of it is a constant time operation with no allocations.







            share|improve this answer














            share|improve this answer



            share|improve this answer








            edited Sep 19 at 16:26

























            answered Sep 19 at 16:21









            ratchet freak

            11.5k1240




            11.5k1240











            • A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication.
              – Toby Speight
              Sep 19 at 16:37










            • This is the insight that people are really looking for during an interview.
              – Tilo
              Sep 19 at 17:56
















            • A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication.
              – Toby Speight
              Sep 19 at 16:37










            • This is the insight that people are really looking for during an interview.
              – Tilo
              Sep 19 at 17:56















            A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication.
            – Toby Speight
            Sep 19 at 16:37




            A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication.
            – Toby Speight
            Sep 19 at 16:37












            This is the insight that people are really looking for during an interview.
            – Tilo
            Sep 19 at 17:56




            This is the insight that people are really looking for during an interview.
            – Tilo
            Sep 19 at 17:56










            up vote
            3
            down vote













            I suppose that a little optimization could be done by changing the way the substrings are extracted from the main string: the iterations should start from the original string itself and then continue by subtracting characters.



            In this way the first time isPalindrome() returns true, the palindrome is the longest one.



            Here is a little edit to your longestPalindrome function:



            int longestPalindrome(std::string& str, std::string& palindromeStr)

            for (int len = str.length(); len > 1; len--) // One-char strings can't be considered as palindromes...

            for (int j = 0; j <= str.length() - len; j++)

            std::string sub = str.substr(j, j + len);
            if (isPalindrome(sub))

            palindromeStr = sub;
            return len;



            return 0; // It is not a palindrome...






            share|improve this answer


























              up vote
              3
              down vote













              I suppose that a little optimization could be done by changing the way the substrings are extracted from the main string: the iterations should start from the original string itself and then continue by subtracting characters.



              In this way the first time isPalindrome() returns true, the palindrome is the longest one.



              Here is a little edit to your longestPalindrome function:



              int longestPalindrome(std::string& str, std::string& palindromeStr)

              for (int len = str.length(); len > 1; len--) // One-char strings can't be considered as palindromes...

              for (int j = 0; j <= str.length() - len; j++)

              std::string sub = str.substr(j, j + len);
              if (isPalindrome(sub))

              palindromeStr = sub;
              return len;



              return 0; // It is not a palindrome...






              share|improve this answer
























                up vote
                3
                down vote










                up vote
                3
                down vote









                I suppose that a little optimization could be done by changing the way the substrings are extracted from the main string: the iterations should start from the original string itself and then continue by subtracting characters.



                In this way the first time isPalindrome() returns true, the palindrome is the longest one.



                Here is a little edit to your longestPalindrome function:



                int longestPalindrome(std::string& str, std::string& palindromeStr)

                for (int len = str.length(); len > 1; len--) // One-char strings can't be considered as palindromes...

                for (int j = 0; j <= str.length() - len; j++)

                std::string sub = str.substr(j, j + len);
                if (isPalindrome(sub))

                palindromeStr = sub;
                return len;



                return 0; // It is not a palindrome...






                share|improve this answer














                I suppose that a little optimization could be done by changing the way the substrings are extracted from the main string: the iterations should start from the original string itself and then continue by subtracting characters.



                In this way the first time isPalindrome() returns true, the palindrome is the longest one.



                Here is a little edit to your longestPalindrome function:



                int longestPalindrome(std::string& str, std::string& palindromeStr)

                for (int len = str.length(); len > 1; len--) // One-char strings can't be considered as palindromes...

                for (int j = 0; j <= str.length() - len; j++)

                std::string sub = str.substr(j, j + len);
                if (isPalindrome(sub))

                palindromeStr = sub;
                return len;



                return 0; // It is not a palindrome...







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited Sep 19 at 11:55

























                answered Sep 19 at 11:36









                rudicangiotti

                1566




                1566



























                     

                    draft saved


                    draft discarded















































                     


                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f203983%2ffind-longest-palindrome-substring%23new-answer', 'question_page');

                    );

                    Post as a guest













































































                    Popular posts from this blog

                    How to check contact read email or not when send email to Individual?

                    Displaying single band from multi-band raster using QGIS

                    How many registers does an x86_64 CPU actually have?