Leetcode 2131: Longest Palindrome by Concatenating Two Letter Words
You are given an array of strings, where each string consists of two lowercase English letters. The task is to create the longest possible palindrome by selecting some of these strings and concatenating them in any order. Each string can be used at most once. A palindrome is a string that reads the same forward and backward. Return the length of the longest palindrome that can be created, or 0 if it’s not possible to create any palindrome.
Problem
Approach
Steps
Complexity
Input: You are given an array of strings where each string has exactly two lowercase English letters.
Example: words = ['ab', 'ba', 'aa', 'bb']
Constraints:
• 1 <= words.length <= 10^5
• words[i].length == 2
• words[i] consists of lowercase English letters.
Output: Return an integer representing the length of the longest palindrome that can be formed using the given strings.
Example: Input: words = ['ab', 'ba', 'aa', 'bb'] Output: 8
Constraints:
• The solution must return the length of the longest possible palindrome.
Goal: The goal is to find pairs of words and possibly one central word to form the longest palindrome.
Steps:
• 1. Iterate through the array of words and count how many of each word exist.
• 2. Look for pairs of words (e.g., 'ab' and 'ba') that can form palindromes when combined.
• 3. If a word consists of identical letters (e.g., 'aa'), count them for potential center placement in the palindrome.
• 4. Return the length of the longest palindrome formed.
Goal: Ensure that the solution is efficient and can handle large inputs as the number of words can go up to 10^5.
Steps:
• The number of words is at most 10^5.
• Each word consists of exactly two lowercase English letters.
Assumptions:
• There will always be a valid input of at least one word.
• The number of words will always be even or odd as per the given constraints.
• Input: Input: words = ['ab', 'ba', 'aa', 'bb']
• Explanation: In this case, 'ab' and 'ba' can form a palindrome pair, and 'aa' and 'bb' can form another. The longest palindrome formed is 'ab' + 'aa' + 'bb' = 'abbbba', which has a length of 8.
• Input: Input: words = ['xx', 'yy', 'zz']
• Explanation: Here, 'xx' can form a palindrome on its own, but 'yy' and 'zz' don't have pairs to form a larger palindrome. The longest palindrome formed is 'xx', which has a length of 2.
Approach: To solve this problem, we need to count pairs of words that can form palindromes and find a potential central word for the palindrome.
Observations:
• We can pair words that are reverse of each other to form the largest possible palindrome.
• We need to track word frequencies and identify pairs and possible center words that can maximize the palindrome length.
Steps:
• 1. Count the frequency of each word in the input array.
• 2. For each word, check if its reverse exists to form pairs and add to the palindrome length.
• 3. If there are any words with identical letters (e.g., 'aa'), use one as the center if no other center is used.
• 4. Return the total length of the longest palindrome.
Empty Inputs:
• Empty input arrays should not be allowed, as the problem guarantees that there will always be words in the list.
Large Inputs:
• Ensure the solution is efficient for the upper limit of the input size (10^5 words).
Special Values:
• When all words are the same (e.g., ['aa', 'aa', 'aa']), only one word can form the center of the palindrome.
Constraints:
• The solution must be efficient in both time and space to handle large inputs.
int longestPalindrome(vector<string>& words) {
int ans = 0;
int unpaired = 0;
unordered_map<string, int> mp;
for(string w: words) {
if(w[0] == w[1]) {
if(mp[w] > 0) {
unpaired--;
ans += 4;
mp[w]--;
} else {
unpaired++;
mp[w]++;
}
} else {
string rev = w;
reverse(rev.begin(), rev.end());
if(mp[rev] > 0) {
ans += 4;
mp[rev]--;
} else mp[w]++;
}
}
if (unpaired > 0) ans += 2;
return ans;
}
1 : Function Definition
int longestPalindrome(vector<string>& words) {
Function definition that initializes the longestPalindrome function which takes a vector of words as input.
2 : Variable Initialization
int ans = 0;
Initializes a variable 'ans' to 0, which will hold the total length of the longest palindrome.
3 : Variable Initialization
int unpaired = 0;
Initializes a counter 'unpaired' to track words that cannot be paired with their reverse.
4 : Data Structure Initialization
unordered_map<string, int> mp;
Declares an unordered map 'mp' to store the frequency of each word.
5 : Loop
for(string w: words) {
Begins a loop to iterate over each word in the input vector.
6 : Condition
if(w[0] == w[1]) {
Checks if the current word consists of two identical characters.
7 : Condition
if(mp[w] > 0) {
If a pair of the same word exists in the map, decrease unpaired count and add 4 to the result.
8 : Action
unpaired--;
Decreases the unpaired count when a matching pair is found.
9 : Action
ans += 4;
Adds 4 to the answer since each word pair contributes 4 to the palindrome.
10 : Action
mp[w]--;
Decreases the frequency of the current word in the map.
11 : Action
} else {
If no pair is found for the word, increase the unpaired count.
12 : Action
unpaired++;
Increases the unpaired count when no matching pair exists.
13 : Action
mp[w]++;
Increases the frequency of the current word in the map.
14 : Condition
} else {
Checks if the current word consists of two different characters.
15 : Action
string rev = w;
Stores the reverse of the current word in the variable 'rev'.
16 : Action
reverse(rev.begin(), rev.end());
Reverses the string 'rev' to check for palindrome matches.
17 : Condition
if(mp[rev] > 0) {
Checks if a reverse pair for the current word exists in the map.
18 : Action
ans += 4;
Adds 4 to the answer when a reverse pair is found.
19 : Action
mp[rev]--;
Decreases the frequency of the reversed word in the map.
20 : Action
} else mp[w]++;
If no reverse pair is found, increase the frequency of the current word in the map.
21 : Final Check
if (unpaired > 0) ans += 2;
If there are any unpaired words left, add 2 to the result to account for one word in the middle of the palindrome.
22 : Return Statement
return ans;
Returns the final length of the longest palindrome that can be formed.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of words, as we only need to iterate through the list and check frequencies.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n), as we store the frequency of each word in a hashmap.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus