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(n2 ).
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)