Problem
Given an array of strings, you need to find the longest running sequence of a character among
all possible permutations of the strings in the array.
INPUT:
ab
ba
aac
OUTPUT:
a,3
Solution
This is the simplest way to solve this problem.
1. Do permutations.
2. Find the longest running sequences in each permutation.
However, this solution is not optimized. Early termination has not been considered if two neighbor strings cannot be concatenated.
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the longest running sequence of a character among all possible
permutations of the strings in the array
Created Date : 26-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <string>
#include <vector>
using namespace std;
void Swap(string& str1, string& str2)
{
string temp = str1;
str1 = str2;
str2 = temp;
}
void FindLongSequence(vector<string> vec, char& ch, int& len)
{
vector<char> vch;
for(int i = 0; i < vec.size(); ++ i){
vch.insert(vch.end(), vec[i].begin(), vec[i].end());
}
int cnt = 1;
char x = vch[0];
for(int i = 1; i < vch.size(); ++i){
if(vch[i] == vch[i-1]){
cnt ++;
}
else{
cnt = 1;
x = vch[i];
}
if(cnt > len){
ch = x;
len = cnt;
}
}
}
void FindLongestRunningSequence(vector<string>& vec, int index, char& ch, int& len)
{
if(index == vec.size()){
FindLongSequence(vec, ch, len);
return;
}
for(int i = index; i < vec.size(); ++i){
Swap(vec[index], vec[i]);
FindLongestRunningSequence(vec, index + 1, ch, len);
Swap(vec[index], vec[i]);
}
}
void DoTest(vector<string>& vec, char& ch, int& len)
{
cout << "-----------------------------------------" << endl;
len = 0;
copy(vec.begin(), vec.end(), ostream_iterator<string>(cout, " "));
cout << endl;
FindLongestRunningSequence(vec, 0, ch, len);
cout << "The length of the longest sequences is " << len << endl;
cout << "The character is " << ch << endl;
vec.clear();
vec.resize(0);
}
int main(int argc, char* argv[])
{
vector<string> vec;
char ch;
int len(0);
vec.push_back("ab");
vec.push_back("ba");
vec.push_back("aac");
DoTest(vec, ch, len);
vec.push_back("ba");
vec.push_back("aac");
vec.push_back("aaaa");
vec.push_back("aaaa");
vec.push_back("azzzzzzzzzzzzzzzzzzzza");
DoTest(vec, ch, len);
vec.push_back("ab");
vec.push_back("bb");
vec.push_back("bbb");
vec.push_back("bbbb");
vec.push_back("ba");
DoTest(vec, ch, len);
vec.push_back("b");
vec.push_back("bb");
vec.push_back("bbb");
vec.push_back("bbbb");
vec.push_back("b");
DoTest(vec, ch, len);
vec.push_back("");
vec.push_back("bb");
vec.push_back("bbb");
vec.push_back("bbbb");
vec.push_back("b");
DoTest(vec, ch, len);
return 0;
}
Output
-----------------------------------------
ab ba aac
The length of the longest sequences is 3
The character is a
-----------------------------------------
ba aac aaaa aaaa azzzzzzzzzzzzzzzzzzzza
The length of the longest sequences is 20
The character is z
-----------------------------------------
ab bb bbb bbbb ba
The length of the longest sequences is 11
The character is b
-----------------------------------------
b bb bbb bbbb b
The length of the longest sequences is 11
The character is b
-----------------------------------------
bb bbb bbbb b
The length of the longest sequences is 10
The character is b
Press any key to continue . . .