Longest Palindrome
A string is a palindrome if it reads the same backward as forwards. For example, “madam” and “racecar” are palindromes, but “milk” is not.
We are given an array of N strings in which each string consist of two lowercase English letters. We would like to join as many strings together as possible in order to obtain a palindrome.
Input
arr: an array of length N containing two-letter strings
Output
the length of longest palindrome that can be created by joining as many strings together as possible form arr
Examples
Example 1:
Input:
arr = ['ck', 'kc', 'ho', 'kc']
Output:
4
Explanation:
The longest palindrome are “ckkc” and “kcck”, and their lengths are both equal to 4.
Solution: Brute Force
int solution(std::vector<std::string> arr) {
int res=0;
bool flag = false;
vector<string> rarr;
vector<bool> val(10000,0);
for(auto st:arr){
swap(st[0],st[1]);
rarr.push_back(st);
}
for(int i=0;i<arr.size();i++){
if(val[i]) continue;
for(int j=i+1;j<arr.size();j++){
if(arr[i] == rarr[j]){
res += 4;
val[i]=1,val[j]=1;
break;
}
}
if(val[i] == 0 && arr[i] == rarr[i]) flag = true;
}
if(flag) res += 2;
return res;
}