Skip to content

Instantly share code, notes, and snippets.

@misterpoloy
Created June 5, 2020 02:56
Show Gist options
  • Save misterpoloy/b3a7af61bccd858fa80ecffd12bb69ff to your computer and use it in GitHub Desktop.
Save misterpoloy/b3a7af61bccd858fa80ecffd12bb69ff to your computer and use it in GitHub Desktop.
#CodeChalenge AlgoExpert Longest palindrome in a string
using namespace std;
vector<int> compareHelper(string str, int startIndex, int endIndex) {
while (startIndex >= 0 && endIndex < str.size()) {
if (str[startIndex] != str[endIndex]) {
break;
}
startIndex--;
endIndex++;
}
return { startIndex + 1, endIndex };
}
int getSize(vector<int>& vec) {
return vec[1] - vec[0];
}
string longestPalindromicSubstring(string str) {
vector<int> longest{0, 1};
for (int i = 1; i < str.size(); i++) {
vector<int> even = compareHelper(str, i - 1, i);
vector<int> odd = compareHelper(str, i - 1, i + 1);
vector<int> currentLong = getSize(even) > getSize(odd) ? even : odd;
if (getSize(longest) < getSize(currentLong)) {
longest = currentLong;
}
}
return str.substr(longest[0], longest[1] - longest[0]);
}
@misterpoloy
Copy link
Author

CodeChallenge

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment