The no. of strings in the input can be maximum 10^6.The maximum length of each string can be 10^6.
I have to find whether the string can be broken into exactly two identical strings just by removing atmost one character from the given string.
For eg.-
"acbab"-this string can be broken into two identical string by removing "c" from the string hence the resultant string becomes "abab" which means two identical string "ab" and "ab".
"adaada"-this string can also be broken into two identical strings "ada"+"ada".
The condition is that we can remove atmost one character from the given string.
I have to run the code in O(n) time complexicity.
please suggest me some method for the above problem.
Well just to give you a place to start, here is a function I whipped up that will tell you if a string with an EVEN amount of characters is splittable or not.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
bool splittableString(string input)
{
int size = input.size();
if (size % 2 == 0) //If even # of characters
{
for (int i = 0; i < (size/2); i++)
{
constint rightindex = (size / 2) + i;
if (input[i] != input[rightindex])
returnfalse;
}
returntrue;
}
//Add logic for if odd # of characters
}
It can be used like
1 2 3
string test = "adab";
if (splittableString(test))
cout << "The string: " << test << " is splittable.";
However, doing this for a string with an odd # of characters is a lot more work. I'm not 100% sure of the best way to approach doing that.