diff options
Diffstat (limited to 'longest_palindrome_concat.cpp')
-rw-r--r-- | longest_palindrome_concat.cpp | 29 |
1 files changed, 29 insertions, 0 deletions
diff --git a/longest_palindrome_concat.cpp b/longest_palindrome_concat.cpp new file mode 100644 index 0000000..3a42e0a --- /dev/null +++ b/longest_palindrome_concat.cpp @@ -0,0 +1,29 @@ +#include "leetcode.h" + +class Solution { +public: + int longestPalindrome(vector<string> &words) { + unordered_map<string, int> um; + for (auto w : words) + ++um[w]; + int ans = 0, center = 0, sz = 2; + for (auto [w, cnt] : um) { + auto reversed = string(rbegin(w), rend(w)); + if (w == reversed) { + ans += 2 * (cnt / 2); + center |= cnt % 2; + } else { + auto it = um.find(reversed); + if (it != end(um)) + ans += min(cnt, it->second); + } + } + return sz * ans + (center ? sz : 0); + } +}; + +int main() { + Solution obj; + vector<string> words = {"lc", "cl", "gg"}; + cout << obj.longestPalindrome(words); +} |