2131. Longest Palindrome by Concatenating Two Letter Words
Problem Solving - Day 33
Hello, reader 👋🏽 ! Welcome to day 33 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Today, I will be picking up LeetCode's daily challenge problem: 2131. Longest Palindrome by Concatenating Two Letter Words .
🤔 Problem Statement
- Given an array of strings words where each element of words consists of two lowercase English letters, return the length of the longest palindrome that can be created. If not, return -1.
- A palindrome can be formed by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.
- E.g.:
words = ["lc", "cl", "gg"]=>6words = ["ab", "lc", "ab"]=>-1words = ["ab", "ty", "yt", "lc", "cl", "ab"]=>8
💬 Thought Process - Traverse Array
From the test cases, the following are the types of strings that can be found in the list of words:
- A word where 1st and 2nd characters are same, e.g.: "aa"
- A word with different characters, e.g.: "ab"
We can include a string with different characters in the palindrome, if the words array also contains the reversed string.
- If there are multiple strings with same characters but they only occur once, then only one set of the word can be included in the palindrome.
If a word with same characters appear in the words array twice, then both the words can be included in the palindrome.
We maintain a count of occurrences of the strings and use the above 3 options and keep decrementing the count.
- Let's look at the below example and find out what we can do:
- We will find the longest palindrome by traversing the array and while looking for the reversed string for every word.
For every word:
- If the characters are different and the reversed string is a part of the array, we will add 4 to the count, simultaneously reducing the count of reversed word and the current word in the map.
- If the characters are same:
- and the string occurs only once, we will include it only if another word with same characters occurring only once was not added before. Then, we will add 2 to the count and reduce the count. For e.g.: if both
"aa"and"bb"occurs only once, then we can only include either of them. - If the string occurs more than once, then we include both occurrence, add 4 to count and reduce the count of the same word by 2 in the map.
- and the string occurs only once, we will include it only if another word with same characters occurring only once was not added before. Then, we will add 2 to the count and reduce the count. For e.g.: if both
We will repeat this until the end of the words array.
👩🏽💻 Solution - Traverse Array
class Solution {
public int longestPalindrome(String[] words) {
int n = words.length;
Map<String, Integer> frequency = getWordsFrequency(words);
int count = 0;
boolean hasDoubleOccurring = false;
for(String word: words) {
char first = word.charAt(0), second = word.charAt(1);
String reversed = "" + second + first;
if(frequency.containsKey(reversed)) {
int wordFreq = frequency.get(word);
if(first == second) {
if(wordFreq > 1) {
count += 4;
wordFreq -= 2;
if(wordFreq == 0) {
frequency.remove(word);
}
else {
frequency.put(word, wordFreq);
}
}
else if(!hasDoubleOccurring) {
// only decrement once
count += 2;
wordFreq -= 1;
hasDoubleOccurring = true;
if(wordFreq == 0) {
frequency.remove(word);
}
else {
frequency.put(word, wordFreq);
}
}
}
else {
int revFreq = frequency.get(reversed);
revFreq-=1;
wordFreq -= 1;
count += 4;
if(revFreq == 0 || wordFreq == 0) {
frequency.remove(reversed);
frequency.remove(word);
}
else {
frequency.put(reversed, revFreq);
frequency.put(word, wordFreq);
}
}
}
}
return count;
}
private Map<String, Integer> getWordsFrequency(String[] words) {
Map<String, Integer> frequency = new HashMap();
for(String word: words) {
if(!frequency.containsKey(word)) {
frequency.put(word, 1);
}
else {
frequency.put(word, frequency.get(word)+1);
}
}
return frequency;
}
}
Time Complexity: O(N)
N = length of words array
Space Complexity: O(min(N, 26^2))
💬 Thought Process - Build From Array
- In this solution, instead of traversing the words array, we will traverse the key strings in the map.
- Few observations to note:
- For words with different characters when the reversed string is present in the array, the total words that can be included in the palindrome is:
min(count[word], count[reversedWord]).- E.g.:
"ab", "ba", ab", we can only include "abba" once asbaonly occurs once.
- E.g.:
- For words with same characters, they can either appear odd or even number of times.
- Words that appear even number of times, we can include the word
count[word]times.- E.g.: If
"aa"appears 4 times, we will include all 4 occurrences.
- E.g.: If
- Words that appear odd number of times, we can include the word
count[word]-1times (even times). The final occurrence can only be included if the palindrome already did not have a word with same characters occurring odd times.- E.g.: If we have the following
"cc", "aa", "aa", "aa", then we will either include all occurrences of"aa"and exclude"cc". Or, we will include two occurrences of"aa"and one occurrence of"cc".
- E.g.: If we have the following
- Words that appear even number of times, we can include the word
- For words with different characters when the reversed string is present in the array, the total words that can be included in the palindrome is:
👩🏽💻 Solution - Traverse Array
class Solution {
public int longestPalindrome(String[] words) {
int n = words.length;
Map<String, Integer> frequency = new HashMap();
for(String word: words) {
if(frequency.containsKey(word)) {
int freq = frequency.get(word);
frequency.put(word, freq+1);
}
else {
frequency.put(word, 1);
}
}
int count = 0;
boolean usedSingleDoubleValue = false;
for(String word: frequency.keySet()) {
char first = word.charAt(0), second = word.charAt(1);
int freq = frequency.get(word);
if(first == second) {
if(freq % 2 == 0) {
count += freq * 2;
}
else {
if(!usedSingleDoubleValue){
count += freq * 2;
usedSingleDoubleValue = true;
}
else {
count += (freq - 1) * 2;
}
}
}
else {
String reversed = "" + second + first;
if(frequency.containsKey(reversed)) {
int revFreq = frequency.get(reversed);
int min = Math.min(revFreq, freq);
count += min*4;
frequency.put(word, freq-min);
frequency.put(reversed, revFreq-min);
}
}
}
return count;
}
}
Time complexity: O(N + min(N, 26^2)).
- Since every word has only 2 characters and the most combination is 26*26, the hashmap would hold 26*26 key value pairs.
Space Complexity: O(min(N, 26^2)).
- There's also another solution that's given on LeetCode which you can check out there.
- You can find the link to the GitHub repo for this question here: 2131. Longest Palindrome by Concatenating Two Letter Words
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!