Mixing
Find longest Palindrome substring
Clash Royale CLAN TAG#URR8PPP
up vote
2
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';
c++ strings interview-questions
asked 1 hour ago
coder
898428
add a comment |Â
up vote
2
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';
c++ strings interview-questions
asked 1 hour ago
coder
898428
add a comment |Â
up vote
2
down vote
favorite
up vote
2
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';
c++ strings interview-questions
asked 1 hour ago
coder
898428
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++ strings interview-questions
c++ strings interview-questions
asked 1 hour ago
coder
898428
asked 1 hour ago
coder
898428
asked 1 hour ago
coder
898428
asked 1 hour ago
coder
898428
asked 1 hour ago
coder
898428
898428
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
4
down vote
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 (either using the static keyword, or in 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)
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.
answered 37 mins ago
Toby Speight
19.1k43697
Perhaps an unnamed namespace would be more idiomatic C++ than using the static keyword.
– user673679
24 mins ago
Yes, agreed. The effect is pretty much the same. I've edited to the more idiomatic form.
– Toby Speight
23 mins ago
add a comment |Â
up vote
1
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...
answered 45 mins ago
rudicangiotti
1366
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
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 (either using the static keyword, or in 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)
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.
answered 37 mins ago
Toby Speight
19.1k43697
Perhaps an unnamed namespace would be more idiomatic C++ than using the static keyword.
– user673679
24 mins ago
Yes, agreed. The effect is pretty much the same. I've edited to the more idiomatic form.
– Toby Speight
23 mins ago
add a comment |Â
up vote
4
down vote
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 (either using the static keyword, or in 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)
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.
answered 37 mins ago
Toby Speight
19.1k43697
Perhaps an unnamed namespace would be more idiomatic C++ than using the static keyword.
– user673679
24 mins ago
Yes, agreed. The effect is pretty much the same. I've edited to the more idiomatic form.
– Toby Speight
23 mins ago
add a comment |Â
up vote
4
down vote
up vote
4
down vote
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 (either using the static keyword, or in 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)
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.
answered 37 mins ago
Toby Speight
19.1k43697
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 (either using the static keyword, or in 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)
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.
answered 37 mins ago
Toby Speight
19.1k43697
edited 22 mins ago
answered 37 mins ago
Toby Speight
19.1k43697
answered 37 mins ago
Toby Speight
19.1k43697
answered 37 mins ago
Toby Speight
19.1k43697
19.1k43697
Perhaps an unnamed namespace would be more idiomatic C++ than using the static keyword.
– user673679
24 mins ago
Yes, agreed. The effect is pretty much the same. I've edited to the more idiomatic form.
– Toby Speight
23 mins ago
add a comment |Â
Perhaps an unnamed namespace would be more idiomatic C++ than using the static keyword.
– user673679
24 mins ago
Yes, agreed. The effect is pretty much the same. I've edited to the more idiomatic form.
– Toby Speight
23 mins ago
Perhaps an unnamed namespace would be more idiomatic C++ than using the static keyword.
– user673679
24 mins ago
Perhaps an unnamed namespace would be more idiomatic C++ than using the static keyword.
– user673679
24 mins ago
Yes, agreed. The effect is pretty much the same. I've edited to the more idiomatic form.
– Toby Speight
23 mins ago
Yes, agreed. The effect is pretty much the same. I've edited to the more idiomatic form.
– Toby Speight
23 mins ago
add a comment |Â
up vote
1
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...
answered 45 mins ago
rudicangiotti
1366
add a comment |Â
up vote
1
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...
answered 45 mins ago
rudicangiotti
1366
add a comment |Â
up vote
1
down vote
up vote
1
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...
answered 45 mins ago
rudicangiotti
1366
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...
answered 45 mins ago
rudicangiotti
1366
edited 26 mins ago
answered 45 mins ago
rudicangiotti
1366
answered 45 mins ago
rudicangiotti
1366
answered 45 mins ago
rudicangiotti
1366
1366
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
