C++

Forum

 
String

samarth123 (53)
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.
Pindrought (305)
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++)
		{
			const int rightindex = (size / 2) + i;
			if (input[i] != input[rightindex])
				return false;
		}
		return true;
	}

	//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.
Last edited on
Topic archived. No new replies allowed.