Longest Palindrome by Concatenating Two Letter Words — LeetCode 2131 Python Solution
MediumGreedyArrayHash TableStringCounting
- Problem
- #2131
- Pattern
- Greedy
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an array of strings words. Each element of words consists of two lowercase English letters.
Example
- Input
- words = ["lc","cl","gg"]
- Output
- 6
- Explanation
- One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Python solution
Python
class Solution:
def longestPalindrome(self, words: List[str]) -> int:
cnt = Counter(words)
ans = x = 0
for k, v in cnt.items():
if k[0] == k[1]:
x += v & 1
ans += v // 2 * 2 * 2
else:
ans += min(v, cnt[k[::-1]]) * 2
ans += 2 if x else 0
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the number of words auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words?
- LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words?
- The Python solution on this page uses O(n), where n is the number of words auxiliary space.
- What topics does LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words cover?
- LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words is tagged Greedy, Array, Hash Table, String and Counting on LeetCode.