Check if given string can be split into two substrings X and Y

Given a string str. The task is to check whether this string can be splitted into two strings X and Y such that

Y is a substring of X
X + Y = str (Here, X+Y means X and Y are concatenated)

Examples :

Input: pleaselea
Output: Yes
str = "please" + "lea", Here "lea" is a substring of "please".

Input: woohoo
Output: Yes
str = "wooh" + "oo", Here "oo" is a substring of "wooh".

Input: split
Output: No

Approaches :

Naive approach:
Simplest approach for this problem is that

Run a loop for different possibilities of string X
Remaining string will be string Y
Check if Y is a substring of X

Time Complexity of this approach will be O(n² ).

Optimized approach:
Here observation is that, Y is required to be a substring of X, that means each character of Y will occur in string X in the same manner. And, Y is always a suffix of given string.

We can optimize our solution by limiting length of Y as 1. We already know that Y is a suffix and will occur in X, so last character of given string must occur in X for the given condition to be fulfilled.

Now, we will take only last character of str as string Y and check if it occurs in string X (first n-1 characters).

Below is the implementation of the above approach:

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;

// function to check if given string 
// can be splitted in X and Y
bool splitString (string str)
{
  int n = str.length();
 
  // string Y
  char Y = str[n - 1];
  
  // find Y in remaining string
  for (int i=0; i<n-1; i++)
  {
    if (str[i] == Y)
      return true;
  }
  	
  return false;
}

// Driver Code
int main()
{
  // Given string
  string str = "pleaselea";
  	
  if (splitString(str))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}

Output:

Yes

Time Complexity: O(n)
Space Complexity: O(n)

Similar Reads