Problem
Given an array with repetition of numbers .Find the maximum length of continuous subarray with at max 3 unique numbers in O(n).
Eg. A: 123143412
output : 6 (314341)
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the maximum length of continuous subarray with at max 3 unique numbers
Created Date : 26-09-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <string>
#include <tuple>
#include <set>
using namespace std;
string FindLongestSubquence(string seq)
{
int maxLen(0);
int maxStart(0);
int start(0);
int len(0);
for(int i = 0; i < seq.size(); ++i){
set<char> s;
int j;
for(j = i; j >= 0 && s.size() <= 3; j--){
s.insert(seq[j]);
}
start = (s.size() > 3) ? j + 2 : 0;
len = i - start + 1;
maxLen = max(maxLen, len);
if(len == maxLen){
maxStart = start;
}
}
cout << "Output : " << maxLen;
cout << " (" << seq.substr(maxStart, maxLen) << ")" << endl;
return seq.substr(maxStart, maxLen);
}
void DoTest(string str)
{
cout << "Input : " << str <<endl;
FindLongestSubquence(str);
cout << "------------------------" << endl;
}
int main(int argc, char* argv[])
{
DoTest("123143412"); // Expect 6 (314341)
DoTest("1231231231"); // Expect 10 (1231231231)
DoTest("0"); // Expect 1 (0);
DoTest("111111"); // Expect 6 (111111)
return 0;
}
Output
Input : 123143412
Output : 6 (314341)
------------------------
Input : 1231231231
Output : 10 (1231231231)
------------------------
Input : 0
Output : 1 (0)
------------------------
Input : 111111
Output : 6 (111111)
------------------------
Press any key to continue . . .